论文标题
时间和空间最佳精确多数人口协议
Time and Space Optimal Exact Majority Population Protocols
论文作者
论文摘要
在本文中，我们研究了受{\ em随机调度程序}管辖的人口协议，该协议在随机下均匀地选择$ n $代理之间的成对相互作用。本文的主要结果是首次和空间最佳{\ em确切的多数人口协议}，它也具有很高的可能性。新协议在最佳{\ em Parallel Time} $ O（\ log n），$中运行，其等效于$ O（n \ log n）$ sequential {\ em pairwise Itsactions}，每个代理都利用$ O（\ log n）$状态的$ o（\ log log n）$ states的最佳数字。 由于本文引入和分析的固定分辨率阶段时钟的新颖概念，新的多数协议的时间最佳性是可能的。新的阶段时钟允许在人群协议中计算大约恒定的并行时间。
In this paper we study population protocols governed by the {\em random scheduler}, which uniformly at random selects pairwise interactions between $n$ agents. The main result of this paper is the first time and space optimal {\em exact majority population protocol} which also works with high probability. The new protocol operates in the optimal {\em parallel time} $O(\log n),$ which is equivalent to $O(n\log n)$ sequential {\em pairwise interactions}, where each agent utilises the optimal number of $O(\log n)$ states. The time optimality of the new majority protocol is possible thanks to the novel concept of fixed-resolution phase clocks introduced and analysed in this paper. The new phase clock allows to count approximately constant parallel time in population protocols.
