Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols

DOI10.1145/3293611.3331627OpenAlexW2962724086MaRDI QIDQ5145176FDOQ5145176

Authors: David Doty, Mahsa Eftekhari 

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

Recommendations

• Simple and fast approximate counting and leader election in populations
• On Counting the Population Size
• Simple and fast approximate counting and leader election in populations
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• scientific article; zbMATH DE number 6850453

zbMATH Keywords

size estimationpopulation protocolstermination

Mathematics Subject Classification ID

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

Cited In (6)

• A survey of size counting in population protocols
• Fast and succinct population protocols for Presburger arithmetic
• On the convergence of population protocols when population goes to infinity
• Composable computation in discrete chemical reaction networks
• Message complexity of population protocols
• Time-space trade-offs in population protocols for the majority problem

This page was built for publication: Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols

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