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

DOI10.1145/3583668.3594589arXiv2302.12508OpenAlexW4380880078WikidataQ130968227 ScholiaQ130968227MaRDI QIDQ6202215FDOQ6202215

Authors: James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser 

Publication date: 26 March 2024

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

Abstract: We analyze the convergence of the $k$-opinion Undecided State Dynamics (USD) in the population protocol model. For $k$=2 opinions it is well known that the USD reaches consensus with high probability within $O(nlogn)$ interactions. Proving that the process also quickly solves the consensus problem for $k>2$ opinions has remained open, despite analogous results for larger $k$ in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on $k$ and on the initial number of undecided agents we prove that the USD achieves plurality consensus within $O(knlogn)$ interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least $Omega(sqrtnlogn)$ we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for $k>2$ for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with $k>2$ which does not need any initial bias.

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

zbMATH Keywords

randomized algorithmspopulation protocolsplurality consensus

Mathematics Subject Classification ID

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

Cites Work

• A simple population protocol for fast robust approximate majority
• Title not available (Why is that?)
• Coalescing random walks and voting on graphs
• Distributed probabilistic polling and applications to proportionate agreement
• Deterministic population protocols for exact majority and plurality
• A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
• Fast and exact majority in population protocols
• Time-space trade-offs in population protocols for the majority problem
• Drift analysis and evolutionary algorithms revisited
• Bounds on the Voter Model in Dynamic Networks
• The Power of Two Choices in Distributed Voting
• Title not available (Why is that?)
• Simple dynamics for plurality consensus
• Fast consensus for voting on general expander graphs
• Simplifying analyses of chemical reaction networks for approximate majority
• Plurality consensus in the gossip model
• Efficient plurality consensus, or: the benefits of cleaning up from time to time
• Nearly-tight analysis for 2-choice and 3-majority consensus dynamics
• A polylogarithmic gossip algorithm for plurality consensus
• Fast plurality consensus in regular expanders
• Recent results in population protocols for exact majority and leader election
• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
• Phase transition of the 3-majority dynamics with uniform communication noise
• A tight analysis of the parallel undecided-state dynamics with two colors
• Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
• Ignore or comply? On breaking symmetry in consensus
• AnO(log^3/2n) Parallel Time Population Protocol for Majority withO(logn) States
• Theory of evolutionary computation. Recent developments in discrete optimization
• On the necessary memory to compute the plurality in multi-agent systems
• Consensus of interacting particle systems on Erdős-Rényi graphs
• Positive Aging Admits Fast Asynchronous Plurality Consensus

This page was built for publication: Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model

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