Time-space trade-offs in population protocols for the majority problem

DOI10.1007/s00446-020-00385-0OpenAlexW3047533640MaRDI QIDQ2025852

Robert Elsässer, Peter Kling, Tom Friedetzky, Tomasz Radzik, Dominik Kaaser, Petra Berenbrink

Publication date: 17 May 2021

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

stochastic processesdistributed computingpopulation protocolsmajority problem

Mathematics Subject Classification ID

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

Related Items

Fast and succinct population protocols for Presburger arithmetic ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Protocols with constant local storage and unreliable communication ⋮ A survey of size counting in population protocols ⋮ Distributed computation with continual population growth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple population protocol for fast robust approximate majority
• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Fast and Exact Majority in Population Protocols
• Convergence Speed of Binary Interval Consensus
• Time-Space Trade-offs in Population Protocols
• A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States
• Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols
• Determining Majority in Networks with Local Interactions and Very Small Local Memory
• Stably computable predicates are semilinear
• Brief Announcement
• Brief Announcement
• Computation in networks of passively mobile finite-state sensors