Stabilizing Consensus with Many Opinions

DOI10.1137/1.9781611974331.CH46MaRDI QIDQ4575624zbMATH OpenOpenAlexFDO

Authors Luca Becchetti, Francesco Pasquale, Luca Trevisan, Andrea Clementi, Emanuele Natale

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.06782, http://epubs.siam.org/doi/10.1137/1.9781611974331.ch46

zbMATH Keywords

Byzantine agreementdistributed consensusgossip modelmajority rulesMarkov chains

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Distributed systems (68M14) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We consider the following distributed consensus problem: Each node in a complete communication network of size $n$ initially holds an emph{opinion}, which is chosen arbitrarily from a finite set $Sigma$. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be emph{valid}, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of an adaptive, malicious adversary who can modify the opinions of a bounded number of nodes in every round. We consider the emph{3-majority dynamics}: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let $k$ be the number of valid opinions. We show that, if $kleqslant{n}^{alpha}$, where $alpha$ is a suitable positive constant, the 3-majority dynamics converges in time polynomial in $k$ and $logn$ with high probability even in the presence of an adversary who can affect up to $o(sqrtn)$ nodes at each round. Previously, the convergence of the 3-majority protocol was known for $|Sigma|=2$ only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for $|Sigma|>2$.

Recommendations

• Consensus and fragmentation of opinions with a focus on bounded confidence
• Practical consensus in bounded confidence opinion dynamics
• When consensus meets self-stabilization
• Consensus in Concatenated Opinion Dynamics With Stubborn Agents
• Stability of multi-valued continuous consensus
• Cluster consensus of opinion dynamics with stubborn individuals
• A computational approach to consensus-finding
• scientific article; zbMATH DE number 1106343
• Reaching a consensus with limited information
• Consensus formation on a simplicial complex of opinions

Cited in

(24)

• MinMax algorithms for stabilizing consensus
• Phase transition of the 2-choices dynamics on core-periphery networks
• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• Phase transition of the 3-majority dynamics with uniform communication noise
• Reach almost sure consensus with only group information
• Simple dynamics for plurality consensus
• A tight analysis of the parallel undecided-state dynamics with two colors
• Nearly-tight analysis for 2-choice and 3-majority consensus dynamics
• Ignore or comply? On breaking symmetry in consensus
• The Maximum Label Propagation Algorithm on Sparse Random Graphs
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• Phase transition of the k-majority dynamics in biased communication models
• Suppression of resilient targets via coordinated swarms
• Approximate majority analyses using tri-molecular chemical reaction networks
• Brief Announcement: Discrete Incremental Voting
• Quasi-majority functional voting on expander graphs
• Phase transition of the 3-majority opinion dynamics with noisy interactions
• Quasi-majority functional voting on expander graphs
• Asynchronous majority dynamics in preferential attachment trees
• Asynchronous majority dynamics on binomial random graphs
• Discrete incremental voting on expanders
• Balanced allocations with the choice of noise
• An analysis of avalanche consensus

This page was built for publication: Stabilizing Consensus with Many Opinions

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