Time-Optimal Leader Election in Population Protocols
Time-Optimal Leader Election in Population Protocols
复制标题
群体协议中的时间最优领导者选举
DOI：
10.1109/tpds.2020.2991771
复制
发表时间：
2020
影响因子：
5.3
通讯作者：
Masuzawa Toshimitsu
中科院分区：
文献类型：
--
作者：
Sudo Yuichi;Ooshita Fukuhito;Izumi Taisuke;Kakugawa Hirotsugu;Masuzawa Toshimitsu
在这篇文章中，我们提出了第一个领导人选举协议的人口协议模型，稳定在O（logn）并行时间内的期望与O（logn）状态每个代理，其中n是代理的数量。给定lg n的一个粗略的知识m，使得m ≥ lg n和m = O（logn），所提出的协议保证了只有一个领导者被选举出来，唯一的领导者永远保持此后。该协议是时间最优的，因为最近证明了任何领导者选举协议都需要Ω（logn）并行时间。
In this article, we present the first leader election protocol in the population protocol model that stabilizes within O(logn) parallel time in expectation with O(logn) states per agent, where n is the number of agents. Given a rough knowledge m of lg n such that m ≥ lg n and m = O(logn), the proposed protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter. This protocol is time-optimal because it was recently proven that any leader election protocol requires Ω(logn) parallel time.