Fast computation by population protocols with a leader
Fast computation by population protocols with a leader
复制标题
DOI：
10.1007/s00446-008-0067-z
复制
发表时间：
2008-09-01
影响因子：
1.3
通讯作者：
Eisenstat, David
中科院分区：
文献类型：
--
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
提出了快速算法，用于在概率人群模型中执行计算。这是标准人口协议模型的一种变体，其中有限状态代理在对手调度程序的控制下成对相互作用，在这种情况下，每个相互作用都可能选择所有对。结果表明，当初始人口中提供独特的领导者时，人口可以模拟一台虚拟寄存器机器，概率很高，其中标准算术操作（例如比较，加法，减法，减法，乘法，乘法以及通过常数划分）可以在O中模拟。 （n log（5）n）使用简单寄存器表示或在O（n log（2）n）中的交互作用，使用更复杂的表示形式，该表示需要额外的O（n log（o（o（o（o））） n） - 互动初始化步骤。中心方法是广泛使用流行病来传播从领导者传播信息，并结合一个基于流行病的相时钟，用于检测何时可能完成这些流行病。应用程序包括将半线性谓词计算成本的成本降低到O（n log（5）n）相互作用，从以前最著名的o（n（n（n（2）log n）相互作用）和对数空间图灵机器的模拟在初始O（n log（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o（o ）亚于，））），使用））））在自然平行模型中，相互作用上的这些界限转化为每个步骤的各个步骤，在这种模型中，每个代理都参与每个时间单元的预期theta（1）相互作用。讨论了开放问题，以及模拟结果，表明可以消除初始领导者假设的可能性。
Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model, in which finite-state agents interact in pairs under the control of an adversary scheduler, where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual register machine with high probability in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log(5) n) interactions using a simple register representation or in O(n log(2) n) interactions using a more sophisticated representation that requires an extra O(n log (O(1)) n)-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Applications include a reduction of the cost of computing a semilinear predicate to O(n log(5) n) interactions from the previously best-known bound of O(n(2) log n) interactions and simulation of a LOG-SPACE Turing machine using O(n log(2) n) interactions per step after an initial O(n log(O(1)) n)-interaction startup phase. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an expected Theta(1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption.