Brief Announcement: Optimal Time and Space Leader Election in Population Protocols

Link:
Autor/in:
Verlag/Körperschaft:
Association for Computing Machinery (ACM)
Erscheinungsjahr:
2020
Medientyp:
Text
Schlagworte:
  • Leader Election
  • Chemical Reaction Networks
  • Dynamic Graphs
  • Algorithms
  • Network Protocols
  • Fault Tolerance
  • Leader Election
  • Chemical Reaction Networks
  • Dynamic Graphs
  • Algorithms
  • Network Protocols
  • Fault Tolerance
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/7b39f996-3214-4e71-9156-3e890eea2c8b