A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States

DOI10.4230/LIPIcs.DISC.2018.10zbMath1497.68034OpenAlexW2899320093MaRDI QIDQ5090899

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

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.disc.2018.10

zbMATH Keywords

randomized algorithmsmajoritypopulation protocols

Mathematics Subject Classification ID

Distributed systems (68M14) Randomized algorithms (68W20) Network protocols (68M12)

Related Items (8)

On convergence and threshold properties of discrete Lotka-Volterra population protocols ⋮ Unnamed Item ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Uniform bipartition in the population protocol model with arbitrary graphs ⋮ A survey of size counting in population protocols ⋮ Time-space trade-offs in population protocols for the majority problem ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ Distributed computation with continual population growth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Fast and Exact Majority in Population Protocols
• Time-Space Trade-offs in Population Protocols
• Plurality consensus in arbitrary graphs : lessons learned from load balancing.
• Determining Majority in Networks with Local Interactions and Very Small Local Memory
• A Polylogarithmic Gossip Algorithm for Plurality Consensus
• Brief Announcement

This page was built for publication: A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States