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

(13)

• A survey of size counting in population protocols
• Brief Announcement
• Fast and succinct population protocols for Presburger arithmetic
• Running time analysis of broadcast consensus protocols
• Uniform bipartition in the population protocol model with arbitrary graphs
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• ppsim: a software package for efficiently simulating and visualizing population protocols
• scientific article; zbMATH DE number 7651155 (Why is no real title available?)
• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• Message complexity of population protocols
• Logarithmic expected-time leader election in population protocol model
• On parallel time in population protocols
• Logarithmic Expected-Time Leader Election in Population Protocol Model

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)