Simple and fast approximate counting and leader election in populations

DOI10.1016/J.IC.2021.104698MaRDI QIDQ2139094zbMATH OpenOpenAlexFDO

Authors Othon Michail, Michail Theofilatos, P. G. Spirakis

Publication date 17 May 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2021.104698

zbMATH Keywords

epidemicapproximate countingcountingleader electionpopulation protocolpolylogarithmic time protocol

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Simple and fast approximate counting and leader election in populations
• Brief announcement: 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
• Polylogarithmic-time leader election in population protocols
• Simple and Efficient Leader Election

Cites work

• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• scientific article; zbMATH DE number 7204593 (Why is no real title available?)
• Brief announcement: Fast approximate counting and leader election in populations
• Computation in networks of passively mobile finite-state sensors
• Computation with finite stochastic chemical reaction networks
• Computing on an anonymous ring
• Deterministic function computation with chemical reaction networks
• Distributed computation in dynamic networks
• Fast computation by population protocols with a leader
• Fast space optimal leader election in population protocols
• How many cooks spoil the soup?
• Mediated population protocols
• Mediated population protocols: leader election and applications
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Naming and counting in anonymous unknown dynamic networks
• On space complexity of self-stabilizing leader election in mediated population protocol
• Passively mobile communicating machines that use restricted space
• Polylogarithmic-time leader election in population protocols
• Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• Space-optimal counting in population protocols
• Stably computable predicates are semilinear
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• The computational power of population protocols
• Time and space optimal counting in population protocols
• Time-space trade-offs in population protocols
• Timing in chemical reaction networks

Cited in

(5)

• A survey of size counting in population protocols
• Brief announcement: Fast approximate counting and leader election in populations
• Population stability. Regulating size in the presence of an adversary
• Simple and fast approximate counting and leader election in populations
• Message complexity of population protocols

This page was built for publication: Simple and fast approximate counting and leader election in populations

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