Fast Graphical Population Protocols
Fast Graphical Population Protocols
复制标题
快速图形人口协议
DOI：
10.4230/lipics.opodis.2021.14
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Joel Rybicki
中科院分区：
文献类型：
--
作者：
Dan Alistarh;Rati Gelashvili;Joel Rybicki
设$G$是一个有$n$个结点的图。在随机种群协议模型中，一组$n$个不可区分的、资源有限的节点通过成对交互共同解决任务。在每次交互中，两个随机选择的邻居首先读取彼此的状态，然后更新它们的本地状态。丰富的研究已经建立了严格的上限和下限的基本任务的复杂性，如多数和领导人选举，在这个模型中，当$G$是一个集团。具体来说，在集团中，这些任务可以快速解决，即，在$n \operatorname{polylog} n$成对交互中，具有高概率，每个节点最多使用$\operatorname{polylog} n$个状态。在这项工作中，我们考虑更一般的设置，其中$G$是一个任意的图形，并提出了一种技术，用于模拟协议设计的全连接网络在任何连接的正则图。我们的主要结果是一个模拟，是有效的许多有趣的图形家庭：大致上，模拟开销是多对数的节点数，和二次的电导图。作为一个示例应用程序，我们表明，在任何正则图与电导$\phi$，领导选举和确切多数可以解决在$\phi^{-2} \cdot\operatorname{polylog} n$两两交互，以高概率，使用最多$\phi^{-2} \cdot \operatorname{polylog} n$状态每个节点。这表明，有快速和空间有效的人口协议的领导人选举和确切多数的图具有良好的扩展性能。我们相信，我们的研究结果将被证明是普遍有用的，因为它们允许有效的技术转移之间的良好混合（集团）的情况下，和未开发的空间设置。
Let $G$ be a graph on $n$ nodes. In the stochastic population protocol model, a collection of $n$ indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other's states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when $G$ is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in $n \operatorname{polylog} n$ pairwise interactions, with high probability, using at most $\operatorname{polylog} n$ states per node. In this work, we consider the more general setting where $G$ is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance $\phi$, both leader election and exact majority can be solved in $\phi^{-2} \cdot n \operatorname{polylog} n$ pairwise interactions, with high probability, using at most $\phi^{-2} \cdot \operatorname{polylog} n$ states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.
DOI：
10.1137/120900368
发表时间：
2012-04
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
C. Cooper;Robert Elsässer;H. Ono;T. Radzik
通讯作者：
C. Cooper;Robert Elsässer;H. Ono;T. Radzik
DOI：
10.1109/focs52979.2021.00104
发表时间：
2022-02
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
David Doty;Mahsa Eftekhari;L. Gąsieniec;Eric E. Severson;P. Uznański;Grzegorz Stachowiak
通讯作者：
David Doty;Mahsa Eftekhari;L. Gąsieniec;Eric E. Severson;P. Uznański;Grzegorz Stachowiak
DOI：
10.1137/1.9781611974782.169
发表时间：
2016-02
期刊：
ArXiv
影响因子：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
通讯作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest