Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election

DOI10.1145/3424659MaRDI QIDQ5056397zbMATH OpenOpenAlexFDO

Authors Grzegorz Stachowiak, Leszek Gąsieniec

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3424659

zbMATH Keywords

distributed algorithmleader electionpopulation protocolsrandomised algorithm

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Polylogarithmic-time leader election in population protocols
• Time-space trade-offs in population protocols
• Brief Announcement
• Leader election requires logarithmic time in population protocols

Cited in

(8)

• Population protocols: beyond runtime analysis
• Fast space optimal leader election in population protocols
• Optimal time and space leader election in population protocols
• Near-optimal leader election in population protocols on graphs
• Dynamic size counting in the population protocol model
• Efficient assignment of identities in anonymous populations
• Sublinear-time collision detection in population protocols with polynomially many states
• Anonymous self-stabilising localisation via spatial population protocols

This page was built for publication: Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election

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