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

DOI10.1145/3583668.3594589MaRDI QIDQ6202215zbMATH OpenOpenAlexWikidataFDO

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)

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)

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.

Cites work

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

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)