Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model

DOI10.1145/3583668.3594589arXiv2302.12508OpenAlexW4380880078MaRDI QIDQ6202215

Felix Biermeier, Dominik Kaaser, Petra Berenbrink, Unnamed Author, James Aspnes, Unnamed Author, Christopher Hahn

Publication date: 26 March 2024

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

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

zbMATH Keywords

randomized algorithmspopulation protocolsplurality consensus

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple population protocol for fast robust approximate majority
• Fast consensus for voting on general expander graphs
• Simplifying analyses of chemical reaction networks for approximate majority
• Distributed probabilistic polling and applications to proportionate agreement
• Time-space trade-offs in population protocols for the majority problem
• Phase transition of the 3-majority dynamics with uniform communication noise
• On the necessary memory to compute the plurality in multi-agent systems
• Simple dynamics for plurality consensus
• Fast and Exact Majority in Population Protocols
• Coalescing random walks and voting on graphs
• Deterministic Population Protocols for Exact Majority and Plurality.
• Drift Analysis and Evolutionary Algorithms Revisited
• A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
• Efficient plurality consensus, or: The benefits of cleaning up from time to time
• Bounds on the Voter Model in Dynamic Networks
• A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States
• Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
• The Power of Two Choices in Distributed Voting
• Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
• On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract
• Theory of Evolutionary Computation
• A Polylogarithmic Gossip Algorithm for Plurality Consensus
• Plurality Consensus in the Gossip Model
• Ignore or Comply?
• AnO(log^3/2n) Parallel Time Population Protocol for Majority withO(logn) States
• Positive Aging Admits Fast Asynchronous Plurality Consensus