# Optimal Time and Space Leader Election in Population Protocols

2 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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 $\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; 2020). 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 novel component 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [31 references]

https://hal.inria.fr/hal-02545348
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Friday, April 17, 2020 - 4:37:38 AM
Last modification on : Wednesday, November 3, 2021 - 8:13:46 AM

### File

main.pdf
Files produced by the author(s)

### Citation

Petra Berenbrink, George Giakkoupis, Peter Kling. Optimal Time and Space Leader Election in Population Protocols. STOC 2020 - 52nd Annual ACM Symposium on Theory of Computing, Jun 2020, Chicago, United States. pp.1-29, ⟨10.1145/3357713.3384312⟩. ⟨hal-02545348⟩

### Metrics

Les métriques sont temporairement indisponibles