On Counting the Population Size

DOI10.1145/3293611.3331631MaRDI QIDQ5145177zbMATH OpenOpenAlexFDO

Authors Petra Berenbrink, Dominik Kaaser, Tomasz Radzik

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/1905.11962

zbMATH Keywords

population sizecountingpopulation protocols

Mathematics Subject Classification ID

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

Recommendations

• A survey of size counting in population protocols
• Simple and fast approximate counting and leader election in populations
• 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
• Space-optimal counting in population protocols

Cited in

(9)

• A survey of size counting in population protocols
• Dynamic size counting in the population protocol model
• Residency index – a tool for measuring the population size
• Uniform bipartition in the population protocol model with arbitrary graphs
• Efficient assignment of identities in anonymous populations
• On the Nonidentifiability of Population Sizes
• Message complexity of population protocols
• An analysis of load-balancing algorithms on edge-Markovian evolving graphs
• Sublinear-time collision detection in population protocols with polynomially many states

This page was built for publication: On Counting the Population Size

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