On Counting the Population Size
On Counting the Population Size
复制标题
论人口规模的计算
DOI：
10.1145/3293611.3331631
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
T. Radzik
中科院分区：
文献类型：
--
作者：
P. Berenbrink;Dominik Kaaser;T. Radzik
我们考虑人口模型中人口规模的计算问题。在该模型中，我们给出了一个由n个相同的智能体组成的分布式系统，这些智能体成对地相互作用，以解决一个共同的任务。在每个时间步长中，均匀随机选择两个相互作用的智能体。在本文中，我们考虑了所谓的统一协议，其中两个智能体在交互时的动作可能不依赖于种群大小n。我们提出了两个种群协议来计算种群的大小：协议Approximate，它以[log n]或[log n]的高概率计算，协议CountExact，它在最优的O（log n）交互中计算精确的种群大小，使用Õ (n)状态。这两个协议也可以转换为稳定的协议，通过使用O（log n）个状态的附加乘法因子，以1的概率给出正确的结果。
We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using Õ (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.
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