Paper Info
Title
Stabilizing Consensus with Many Opinions
Abstract
We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 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 k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to o([EQUATION]) nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 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 |Σ| > 2.
Year
DOI
Venue
2015
10.5555/2884435.2884481
SODA '16: Symposium on Discrete Algorithms Arlington Virginia January, 2016
Field
DocType
Volume
Consensus,Convergence (routing),Discrete mathematics,Binary logarithm,Combinatorics,Finite set,Polynomial,Computer science,Markov chain,Majority rule,Bounded function
Journal
abs/1508.06782
ISBN
Citations 
PageRank 
978-1-61197-433-1
10
0.64
References 
Authors
15
5
Name
Order
Citations
PageRank
Luca Becchetti194555.75
Andrea E. F. Clementi2116885.30
Emanuele Natale37414.52
Francesco Pasquale442128.22
Luca Trevisan52995232.34