Optimal time and space leader election in population protocols

Population protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state.

A significant amount of work has been devoted to the study of the time and space complexity of this problem. Alistarh et al. (SODA'17) have shown that Ω(log log n) states per agent are needed in order to elect a leader in fewer than Θ(n 2 ) expected interactions. Moreover, Ω(n log n) expected interactions are required regardless of the number of states (Sudo and Masuzawa, 2019). On the upper bound side, Gasieniec and Stachowiak (SODA'18) have presented the first protocol that uses an optimal, Θ(log log n), number or states and elects a leader in O(n log 2 n) expected interactions. This running time was subsequently improved to O(n log n log log n) (Gasieniec et al., SPAA'19).

In this paper we provide the first leader election population protocol that is both time and space optimal: it uses Θ(log log n) states per agent, and elects a leader in O(n log n) interactions in expectation. A key novel component of our approach is a simple protocol that efficiently selects a small set of agents, of poly(log n) size, given an initial set of s = O(n ϵ ) selected agents. Unlike existing approaches, which proceed by shrinking the initial set monotonically over time, our protocol first increases the set in a controlled way to a specific size (which is independent of s), before it shrinks the set to a poly(log n) size.