Optimal time and space leader election in population protocols

DOI10.1145/3357713.3384312MaRDI QIDQ5144902zbMATH OpenOpenAlexFDO

Authors Petra Berenbrink, George Giakkoupis, Peter Kling

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-02545348

zbMATH Keywords

leader electionpopulation protocolsstabilization time

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Fast space optimal leader election in population protocols
• Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election
• Polylogarithmic-time leader election in population protocols
• Leader election requires logarithmic time in population protocols
• Logarithmic expected-time leader election in population protocol model

Cited in

(24)

• On parallel time in population protocols
• ppsim: a software package for efficiently simulating and visualizing population protocols
• Running time analysis of broadcast consensus protocols
• Uniform bipartition in the population protocol model with arbitrary graphs
• A survey of size counting in population protocols
• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• Logarithmic Expected-Time Leader Election in Population Protocol Model
• Brief Announcement
• scientific article; zbMATH DE number 7651155 (Why is no real title available?)
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• Fast and succinct population protocols for Presburger arithmetic
• Message complexity of population protocols
• Logarithmic expected-time leader election in population protocol model
• Near-optimal leader election in population protocols on graphs
• Majority consensus thresholds in competitive Lotka-Volterra populations
• Brief announcement: Optimally encoding information in chemical reaction networks
• Dynamic size counting in the population protocol model
• Game dynamics and equilibrium computation in the population protocol model
• Efficient assignment of identities in anonymous populations
• Complete graph identification in population protocols
• Sublinear-time collision detection in population protocols with polynomially many states
• The expressive power of population protocols with logarithmic space
• Time-optimal self-stabilizing leader election in population protocols
• Anonymous self-stabilising localisation via spatial population protocols

This page was built for publication: Optimal time and space leader election in population protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144902)