Leader Election Requires Logarithmic Time in Population Protocols

2019/06/25 by Yuichi Sudo, Sudo, Yuichi, Toshimitsu Masuzawa +1 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1906.11121

openalex publication_date 2019/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper shows that every leader election protocol requires logarithmic stabilization time both in expectation and with high probability in the population protocol model. This lower bound holds even if each agent has knowledge of the exact size of a population and is allowed to use an arbitrarily large number of agent states. This lower bound concludes that the protocol given in [Sudo et al., SSS 2019] is time-optimal in expectation.

Cited by

• Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election
• Space-efficient population protocols for exact majority on general graphs
• Content-Oblivious Leader Election in 2-Edge-Connected Networks

Related

• Logarithmic Expected-Time Leader Election in Population Protocol Model
• Time-optimal Loosely-stabilizing Leader Election in Population Protocols
• Population protocols for leader election and exact majority with O(log² n) states and O(log² n) convergence time
• Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
• Almost logarithmic-time space optimal leader election in population\n protocols