03/08/2020

Brief announcement: Optimal time and space leader election in population protocols

Petra Berenbrink, George Giakkoupis, Peter Kling

Keywords: population protocols, leader election, stabilization time

Abstract: Population protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. Recently, 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 Ω (log log n) states per agent are needed to elect a leader in fewer than [EQUATION] expected interactions (Alistarh et al.; SODA’17) and that Ω (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 Θ(log log n) number or states and elects a leader in O(n log2 n) expected interactions. This running time was subsequently improved to O(n log n log log n) (Gasieniec et al.; SPAA’19). We provide 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 Θ(log log n) states per agent. A novel component is a simple protocol that efficiently selects a small set of agents of polylog n size, given O(n∈) initially selected agents. Unlike existing approaches, which monotonically shrink this initially selected set, we first grow it in a controlled way to a specific size before shrinking it again.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers