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

DOI10.1145/3293611.3331627MaRDI QIDQ5145176zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

population protocolssize estimationtermination

Mathematics Subject Classification ID

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

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

Cited in

(11)

• On the convergence of population protocols when population goes to infinity
• Time-space trade-offs in population protocols for the majority problem
• Composable computation in discrete chemical reaction networks
• A survey of size counting in population protocols
• Fast and succinct population protocols for Presburger arithmetic
• Message complexity of population protocols
• Sampling and output estimation in distributed algorithms and LCAs
• Dynamic size counting in the population protocol model
• 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

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)