Stable leader election in population protocols requires linear time

DOI10.1007/s00446-016-0281-zzbMath1451.68041arXiv1502.04246OpenAlexW2743261842MaRDI QIDQ5915694

David Doty, David Soloveichik

Publication date: 13 August 2018

Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.04246

zbMATH Keywords

leader electionchemical reaction networkpopulation protocolstime lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14) Network protocols (68M12)

Related Items (25)

Polylogarithmic-Time Leader Election in Population Protocols ⋮ Simple and fast approximate counting and leader election in populations ⋮ ppsim: a software package for efficiently simulating and visualizing population protocols ⋮ Unnamed Item ⋮ Population protocols with unreliable communication ⋮ Leader Election Requires Logarithmic Time in Population Protocols ⋮ Constant-Space Population Protocols for Uniform Bipartition ⋮ Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks ⋮ Speed faults in computation by chemical reaction networks ⋮ Computing with chemical reaction networks: a tutorial ⋮ Unnamed Item ⋮ Protocols with constant local storage and unreliable communication ⋮ Simple and Efficient Leader Election ⋮ Running time analysis of broadcast consensus protocols ⋮ Uniform bipartition in the population protocol model with arbitrary graphs ⋮ Automatic Analysis of Expected Termination Time for Population Protocols ⋮ A survey of size counting in population protocols ⋮ Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits ⋮ Stable leader election in population protocols requires linear time ⋮ Unnamed Item ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ Loosely-stabilizing leader election with polylogarithmic convergence time ⋮ Composable computation in discrete chemical reaction networks ⋮ Robustness of Expressivity in Chemical Reaction Networks ⋮ How many cooks spoil the soup?

Cites Work

• Unnamed Item
• A simple population protocol for fast robust approximate majority
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• Space-optimal counting in population protocols
• Speed faults in computation by chemical reaction networks
• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Parallel program schemata
• Fast and Exact Majority in Population Protocols
• Polylogarithmic-Time Leader Election in Population Protocols
• Time-Space Trade-offs in Population Protocols
• Timing in chemical reaction networks
• Stable leader election in population protocols requires linear time

This page was built for publication: Stable leader election in population protocols requires linear time