We study a plurality-consensus process in which each of n anonymous agents of a communication network initially supports a color chosen from the set [k]. Then, in every round, each agent can revise his color according to the colors currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large biass towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by s additional nodes. The goal is having the process to converge to the stable configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time (Formula presented.) with high probability, provided that (Formula presented.). We then prove that our upper bound above is tight as long as (Formula presented.). This fact implies an exponential time-gap between the plurality-consensus process and the median process (see Doerr et al. in Proceedings of the 23rd annual ACM symposium on parallelism in algorithms and architectures (SPAA’11), pp 149–158. ACM, 2011). A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R., & Trevisan, L. (2017). Simple dynamics for plurality consensus. DISTRIBUTED COMPUTING, 30(4), 293-306 [10.1007/s00446-016-0289-4].

Simple dynamics for plurality consensus

CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2017

Abstract

We study a plurality-consensus process in which each of n anonymous agents of a communication network initially supports a color chosen from the set [k]. Then, in every round, each agent can revise his color according to the colors currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large biass towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by s additional nodes. The goal is having the process to converge to the stable configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time (Formula presented.) with high probability, provided that (Formula presented.). We then prove that our upper bound above is tight as long as (Formula presented.). This fact implies an exponential time-gap between the plurality-consensus process and the median process (see Doerr et al. in Proceedings of the 23rd annual ACM symposium on parallelism in algorithms and architectures (SPAA’11), pp 149–158. ACM, 2011). A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
English
Distributed randomized algorithms; Dynamics; Markov chains; Plurality consensus.
Becchetti, L., Clementi, A., Natale, E., Pasquale, F., Silvestri, R., & Trevisan, L. (2017). Simple dynamics for plurality consensus. DISTRIBUTED COMPUTING, 30(4), 293-306 [10.1007/s00446-016-0289-4].
Becchetti, L; Clementi, A; Natale, E; Pasquale, F; Silvestri, R; Trevisan, L
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
becchetti2017simple.pdf

accesso solo dalla rete interna

Licenza: Copyright dell'editore
Dimensione 557.37 kB
Formato Adobe PDF
557.37 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: http://hdl.handle.net/2108/187093
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 10
social impact