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 Ω(loglogn) states per agent are needed in order to elect a leader in fewer than Θ(n 2) expected interactions. Moreover, Ω(nlogn) 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, Θ(loglogn), number or states and elects a leader in O(n log2 n) expected interactions. This running time was subsequently improved to O(n lognloglogn) (Gasieniec et al., SPAA’19).