Fast and Exact Majority in Population Protocols

DOI10.1145/2767386.2767429zbMath1333.68039OpenAlexW2026030032MaRDI QIDQ2796240

Milan Vojnovic, Rati Gelashvili, Dan Alistarh

Publication date: 23 March 2016

Published in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2767386.2767429

zbMATH Keywords

randomized algorithmspopulation protocolsmajority computation

Mathematics Subject Classification ID

Distributed systems (68M14) Randomized algorithms (68W20)

Related Items (29)

Population protocols with faulty interactions: the impact of a leader ⋮ Data Collection in Population Protocols with Non-uniformly Random Scheduler ⋮ Unnamed Item ⋮ Advances in parameterized verification of population protocols ⋮ On convergence and threshold properties of discrete Lotka-Volterra population protocols ⋮ Constant-Space Population Protocols for Uniform Bipartition ⋮ Fast and succinct population protocols for Presburger arithmetic ⋮ Unnamed Item ⋮ Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model ⋮ Population protocols: beyond runtime analysis ⋮ Protocols with constant local storage and unreliable communication ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fault-tolerant simulation of population protocols ⋮ Mediated Population Protocols: Leader Election and Applications ⋮ Running time analysis of broadcast consensus protocols ⋮ Automatic Analysis of Expected Termination Time for Population Protocols ⋮ A survey of size counting in population protocols ⋮ Determining majority in networks with local interactions and very small local memory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stable leader election in population protocols requires linear time ⋮ Time-space trade-offs in population protocols for the majority problem ⋮ Unnamed Item ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ Loosely-stabilizing leader election with polylogarithmic convergence time ⋮ Towards efficient verification of population protocols ⋮ A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States ⋮ Stochastic analysis of average-based distributed algorithms

Cites Work

• Memorization and Association on a Realistic Neural Model
• Unnamed Item

This page was built for publication: Fast and Exact Majority in Population Protocols