Session 1C - Optimal Time and Space Leader Election in Population Protocols

STOC 2020

Session 1C - Optimal Time and Space Leader Election in Population Protocols

Sep 19, 2020
|
23 views
Details
Population protocols are a model of distributed computing, where $n$ agents with limited computational power and memory perform randomly scheduled pairwise interactions. A significant amount of work has been devoted to the study of the time and space complexity of leader election in this model. It is known that $\Omega(\log\log n)$ states per agent are needed to elect a leader in fewer than $\tilde\Theta(n^2)$ expected interactions (Alistarh et al.; 2017) and that $\Omega(n\log n)$ expected interactions are required regardless of the number of states (Sudo and Masuzawa; 2020). On the positive side, Gasieniec and Stachowiak (SODA'18) gave 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.; 2019). In this talk we present the first leader election population protocol that is both time and space optimal, electing a leader in $O(n\log n)$ expected interactions and using $\Theta(\log\log n)$ states per agent. Joint work with Petra Berenbrink and George Giakkoupis.

Comments
loading...