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

countingpopulation protocolspopulation size

Mathematics Subject Classification ID

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

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

(11)

• Uniform bipartition in the population protocol model with arbitrary graphs
• A survey of size counting in population protocols
• On the Nonidentifiability of Population Sizes
• Residency index – a tool for measuring the population size
• Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols
• Message complexity of population protocols
• Dynamic size counting in the population protocol model
• Efficient assignment of identities in anonymous populations
• An analysis of load-balancing algorithms on edge-Markovian evolving graphs
• 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: 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)