Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority
Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority
复制标题
简短公告：解决绝对多数的时空最优稳定种群协议
DOI：
10.1145/3465084.3467942
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Uznański, Przemyslaw
中科院分区：
文献类型：
--
作者：
Doty, David;Eftekhari, Mahsa;Gąsieniec, Leszek;Severson, Eric;Stachowiak, Grzegorz;Uznański, Przemyslaw
我们研究了种群协议，这是一种分布式计算模型，其中代理以成对交互的方式交换信息，但无法控制其交互伙伴的调度。经过充分研究的多数问题是在最初的n个代理人中确定是否有更多的A、更多的B或平局，每个代理人都有两种意见A或B中的一种。稳定的协议最终以概率1解决这个问题，方法是进入一种配置，在该配置中，所有代理都同意正确的共识决策A、B或T，共识不会改变。我们描述了一个使用O(Logn)状态(loglogn+O(1)位内存)和最优期望时间O(Logn)来解决该问题的协议。已知的状态数O(Logn)对于一类多对数时间稳定协议是最优的，所述多对数时间稳定协议是“输出占优”和“单调”的。这是我们的协议满足的两个自然约束，使其对该类同时具有时间和状态最优。我们的协议是不一致的：转移函数中编码了值logn。我们证明了该协议可以被修改为一致的，同时将状态复杂度增加到Θ(logn，loglogn)。
We study population protocols, a model of distributed computing where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied 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 that solves 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 the class of polylogarithmic time stable protocols that are "output dominant'' and "monotone''. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. 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).
登录
查看更多内容
群体协议中的时间最优自稳定领导者选举
DOI：
10.1145/3465084.3467898
发表时间：
2021
期刊：
PODC 2021: Proceedings of the 40th ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Burman, Janna;Chen, Ho-Lin;Chen, Hsueh-Ping;Doty, David;Nowak, Thomas;Severson, Eric;Xu, Chuan
通讯作者：
Xu, Chuan
影响因子：
1.3
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
通讯作者：
Eisenstat, David
DOI：
10.1109/nca.2016.7778621
发表时间：
2016
期刊：
2016 IEEE 15th International Symposium on Network Computing and Applications (NCA)
影响因子：
--
作者：
Yves Mocquard;E. Anceaume;B. Sericola
通讯作者：
B. Sericola
具有 O(log n) 状态的多数的 O(log3/2 n) 并行时间填充协议
DOI：
10.1145/3382734.3405747
发表时间：
2020
期刊：
Proceedings of the 39th Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Stav Ben;T. Kopelowitz;Matan Kraus;E. Porat
通讯作者：
E. Porat
群体协议中的快速空间最优领导者选举
DOI：
10.1137/1.9781611975031.169
发表时间：
2017
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
L. Gąsieniec;Grzegorz Stachowiak
通讯作者：
Grzegorz Stachowiak