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

DOI10.1007/S00446-020-00385-0OpenAlexW3047533640MaRDI QIDQ2025852FDOQ2025852

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

Recommendations

• Time-space trade-offs in population protocols
• scientific article; zbMATH DE number 6850453
• Fast and exact majority in population protocols
• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• Recent results in population protocols for exact majority and leader election

zbMATH Keywords

stochastic processesdistributed computingpopulation protocolsmajority problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• A survey of size counting in population protocols
• Distributed computation with continual population growth
• Fast and succinct population protocols for Presburger arithmetic
• Protocols with constant local storage and unreliable communication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• On approximate majority and probabilistic time

This page was built for publication: Time-space trade-offs in population protocols for the majority problem

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