Skip to Main content Skip to Navigation
Conference papers

Optimal Time and Space Leader Election in Population Protocols

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-02545348
Contributor : George Giakkoupis <>
Submitted on : Friday, April 17, 2020 - 4:37:38 AM
Last modification on : Wednesday, June 24, 2020 - 4:19:56 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02545348, version 1

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. ⟨hal-02545348⟩

Share

Metrics

Record views

155

Files downloads

328