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 \emph{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 $\Omega(\log\log n)$ states per agent are needed in order to elect a leader in fewer than $\tilde \Theta(n^2)$ expected interactions. Moreover, $\Omega(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, $\Theta(\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 $\Theta(\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^\epsilon)$ 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.