Optimal proportion computation with population protocols
Optimal proportion computation with population protocols
复制标题
使用总体协议计算最佳比例
DOI：
10.1109/nca.2016.7778621
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
B. Sericola
中科院分区：
文献类型：
--
作者：
Yves Mocquard;E. Anceaume;B. Sericola
群体协议的计算模型是一种形式，允许分析大量匿名有限状态代理之间的简单和两两交互产生的特性。到目前为止，已经做了大量的工作来确定在这个模型中哪些问题是可解决的，以及在代理使用的状态和收敛所需的时间方面需要付出多大的代价。本文处理的问题是总体比例问题：每个智能体在A或B两种状态中的一种独立地开始，目标是每个智能体确定最初从状态A开始的智能体的比例，假设每个智能体只使用一组有限的状态，并且不知道有n个智能体。我们提出了一种解决方案，保证在存在统一概率调度程序的情况下，每个智能体在交互O（log n）次后以任意高概率输出具有任意精度ε∈(0,1)的总体比例。每个智能体保持的状态数是最优的，等于2≤≤3/(4ε)≤1。最后，我们证明了我们的解在时间和空间上是最优的，以解决计数问题，比例问题的推广。最后，仿真结果验证了我们的理论分析。
The computational model of population protocols is a formalism that allows the analysis of properties emerging from simple and pairwise interactions among a very large number of anonymous finite-state agents. Significant work has been done so far to determine which problems are solvable in this model and at which cost in terms of states used by the agents and time needed to converge. The problem tackled in this paper is the population proportion problem: each agent starts independently from each other in one of two states, say A or B, and the objective is for each agent to determine the proportion of agents that initially started in state A, assuming that each agent only uses a finite set of states, and does not know the number n of agents. We propose a solution which guarantees that in presence of a uniform probabilistic scheduler every agent outputs the population proportion with any precision ε ∈ (0, 1) with any high probability after having interacted O(log n) times. The number of states maintained by every agent is optimal and is equal to 2⌈3/(4ε)⌉+1. Finally, we show that our solution is optimal in time and space to solve the counting problem, a generalization of the proportion problem. Finally, simulation results illustrate our theoretical analysis.
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