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 logn with high probability even in the presence of an adversary who can affect up to o(√n) 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.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Trevisan, L. (2016). Stabilizing consensus with many opinions. In Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (pp.620-635). Association for Computing Machinery [10.1137/1.9781611974331.ch46].

Stabilizing consensus with many opinions

CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2016-01-01

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 logn with high probability even in the presence of an adversary who can affect up to o(√n) 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.
27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
usa
2016
27
SIAM-ACM
Rilevanza internazionale
contributo
2016
Settore INF/01 - INFORMATICA
English
Byzantine agreement; Distributed consensus; Gossip model; Majority rules; Markov chains;
http://dl.acm.org/citation.cfm?id=2884435.2884481
Intervento a convegno
Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Trevisan, L. (2016). Stabilizing consensus with many opinions. In Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (pp.620-635). Association for Computing Machinery [10.1137/1.9781611974331.ch46].
Becchetti, L; Clementi, A; Natale, E; Pasquale, F; Trevisan, L
File in questo prodotto:
File Dimensione Formato  
becchetti2016stabilizing.pdf

solo utenti autorizzati

Licenza: Copyright dell'editore
Dimensione 279.68 kB
Formato Adobe PDF
279.68 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/170295
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 43
  • ???jsp.display-item.citation.isi??? ND
social impact