We study Plurality Consensus in the QOSSTP Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents supporting any other color by a sufficiently-large bias, though the initial plurality itself might be very far from absolute majority. The goal is to provide a protocol that, with high probability, brings the system into the configuration in which all agents support the (initial) plurality color. We consider the Undecided-State Dynamics, a well-known protocol which uses just one more state (the undecided one) than those necessary to store colors. We show that the speed of convergence of this protocol depends on the initial color configuration as a whole, not just on the gap between the plurality and the second largest color community. This dependence is best captured by a novel notion we introduce, namely, the monochromatic distance md(c) which measures the distance of the initial color configuration c from the closest monochromatic one. In the complete graph, we prove that, for a wide range of the input parameters, this dynamics converges within 0(md(c)log n) rounds. We prove that this upper bound is almost tight in the strong sense: Starting from any color configuration c, the convergence time is f2(md(c)). Finally, we adapt the Undecided-State Dynamics to obtain a fast, random walk-based protocol for plurality consensus on regular expanders. This protocol converges in 0(md(c) polylog(n)) rounds using only polylog(n) local memory. A key-ingredient to achieve the above bounds is a new analysis of the maximum node congestion that results from performing n parallel random walks on regular expanders. All our bounds hold with high probability.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R. (2015). Plurality consensus in the gossip model. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp.371-390). Association for Computing Machinery [10.1137/1.9781611973730.27].

Plurality consensus in the gossip model

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

Abstract

We study Plurality Consensus in the QOSSTP Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents supporting any other color by a sufficiently-large bias, though the initial plurality itself might be very far from absolute majority. The goal is to provide a protocol that, with high probability, brings the system into the configuration in which all agents support the (initial) plurality color. We consider the Undecided-State Dynamics, a well-known protocol which uses just one more state (the undecided one) than those necessary to store colors. We show that the speed of convergence of this protocol depends on the initial color configuration as a whole, not just on the gap between the plurality and the second largest color community. This dependence is best captured by a novel notion we introduce, namely, the monochromatic distance md(c) which measures the distance of the initial color configuration c from the closest monochromatic one. In the complete graph, we prove that, for a wide range of the input parameters, this dynamics converges within 0(md(c)log n) rounds. We prove that this upper bound is almost tight in the strong sense: Starting from any color configuration c, the convergence time is f2(md(c)). Finally, we adapt the Undecided-State Dynamics to obtain a fast, random walk-based protocol for plurality consensus on regular expanders. This protocol converges in 0(md(c) polylog(n)) rounds using only polylog(n) local memory. A key-ingredient to achieve the above bounds is a new analysis of the maximum node congestion that results from performing n parallel random walks on regular expanders. All our bounds hold with high probability.
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
usa
2015
ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)
Rilevanza internazionale
contributo
2015
Settore INF/01 - INFORMATICA
English
Gossip algorithms; Markov chains; Plurality consensus; Random walks;
http://epubs.siam.org/doi/10.1137/1.9781611973730.27
Intervento a convegno
Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R. (2015). Plurality consensus in the gossip model. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp.371-390). Association for Computing Machinery [10.1137/1.9781611973730.27].
Becchetti, L; Clementi, A; Natale, E; Pasquale, F; Silvestri, R
File in questo prodotto:
File Dimensione Formato  
bcnps_soda15.pdf

solo utenti autorizzati

Licenza: Copyright dell'editore
Dimensione 355.35 kB
Formato Adobe PDF
355.35 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/184492
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 46
  • ???jsp.display-item.citation.isi??? ND
social impact