Space-Optimal Counting in Population Protocols
Space-Optimal Counting in Population Protocols
复制标题
群体协议中的空间优化计数
DOI：
10.1007/978-3-662-48653-5_42
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Sohier
中科院分区：
文献类型：
--
作者：
J. Beauquier;Janna Burman;Simon Clavière;D. Sohier
在本文中，我们研究计数的基本问题，即计算系统的大小。我们考虑有限状态群体协议的分布式通信模型，匿名和异步移动设备代理根据公平条件成对通信。这项工作在精确的空间复杂度方面显着改进了该模型中先前已知的计数结果。我们提出并证明了第一个空间最优协议的正确性，解决了两种经典类型的公平性（全局公平性和弱公平性）的问题。两种协议都不需要对计数代理进行初始化。
令人惊讶的是，为全球公平而设计的协议，每个被计数的代理仅使用一位内存的两个状态。该协议在弱公平性下运行，需要每个计数代理所需的 $$\log P$$ 位 P 状态才能计数到 P 个代理。有趣的是，该协议利用了有趣的自然数格罗斯序列，该序列也用于解决中国环和河内塔难题。
In this paper, we study the fundamental problem of counting, which consists in computing the size of a system. We consider the distributed communication model of population protocols of finite state, anonymous and asynchronous mobile devices agents communicating in pairs according to a fairness condition. This work significantly improves the previous results known for counting in this model, in terms of exact space complexity. We present and prove correct the first space-optimal protocols solving the problem for two classical types of fairness, global and weak. Both protocols require no initialization of the counted agents.
The protocol designed for global fairness, surprisingly, uses only one bit of memory two states per counted agent. The protocol, functioning under weak fairness, requires the necessary $$\log P$$ bits P states, per counted agent to be able to count up to P agents. Interestingly, this protocol exploits the intriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Rings and the Hanoi Towers puzzles.
群体协议中的时间和空间优化计数
影响因子：
--
作者：
Aspnes, James;Beauquier, Joffroy;Burman, Janna;Sohier, Devan
通讯作者：
Sohier, Devan