A survey of size counting in population protocols
A survey of size counting in population protocols
复制标题
人口方案中规模计数的调查
DOI：
10.1016/j.tcs.2021.08.038
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Eftekhari, Mahsa
中科院分区：
文献类型：
--
作者：
Doty, David;Eftekhari, Mahsa
人口协议模型描述了一个由n个匿名代理组成的网络，这些代理无法控制与谁交互。代理集体通过随机的两两交互解决计算问题，每个代理更新自己的状态以响应看到其他代理的状态。居群协议相当于化学反应网络模型，描述的是A+ B→C+ D等抽象的化学反应，其中C+ D受限于所有反应都有两个反应物和两个生成物，且所有速率常数都为1。计数问题是设计一个协议，使n个智能体都从相同的状态开始，最终收敛到每个智能体在其状态下编码人口规模n的精确或近似描述的状态。在这篇调查论文中，我们描述了计数问题的最新算法进展。
The population protocol model describes a network of n anonymous agents who cannot control with whom they interact. The agents collectively solve a computational problem through random pairwise interactions, each agent updating its state in response to seeing the state of the other agent. Population protocols are equivalent to the model of chemical reaction networks, describing abstract chemical reactions such as A+ B→ C+ D, when the latter is subject to the restriction that all reactions have two reactants and two products, and all rate constants are 1. The counting problem is that of designing a protocol so that n agents, all starting in the same state, eventually converge to states where each agent encodes in its state an exact or approximate description of population size n. In this survey paper, we describe recent algorithmic advances on the counting problem.
登录
查看更多内容
影响因子：
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
确定性负载均衡方案的改进分析
DOI：
10.1145/2767386.2767413
发表时间：
2014
期刊：
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
P. Berenbrink;R. Klasing;A. Kosowski;Frederik Mallmann;P. Uznański
通讯作者：
P. Uznański