Time-Optimal Leader Election in Population Protocols
Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, Toshimitsu Masuzawa · IEEE Transactions on Parallel and Distributed Systems · 2020
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.