A time and space optimal stable population protocol solving exact majority
A time and space optimal stable population protocol solving exact majority
复制标题
DOI：
10.1109/focs52979.2021.00104
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
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
我们研究人口协议，这是一种适用于混合化学反应网络和其他物理系统的分布式计算模型，在成对相互作用中，代理人交换信息，但无法控制其相互作用伙伴的时间表。最初的$ n $代理人，每个人都有两个意见$ a $或b之一，无论a，更多的b还是一个稳定的协议，都可以通过输入概率1来解决此问题。所有代理商都同意A，B或T的正确共识决定，我们可以使用O（log n）状态来描述解决此问题的协议（日志$ n $ + o（1）位内存）和最佳预期时间$ o $（log $ n $）。 1]。函数在其中具有编码的值[log $ n $]。
We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The majority problem is that of determining in an initial population of $n$ agents, each with one of two opinions $A$ or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol solving this problem using O(log n) states (log log $n$ + O(1) bits of memory) and optimal expected time $O$(log $n$). The number of states $O$(log $n$) is known to be optimal for polylogarithmic time stable protocols that are “output dominant” and “monotone” [1]. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. We introduce a key technique called a “fixed resolution clock” to achieve partial synchronization. Our protocol is nonuniform: the transition function has the value [log $n$] encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ (log $n$ log log n).