We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a color chosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors. The goal (of the agents) is to let the process converge to the stable configuration where all nodes support the plurality color. It is assumed that the initial color configuration has a sufficiently large bias s, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by an additive value s. 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 that each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly at random). We prove a tight bound on the convergence time which grows as ⊖(k log n) for a wide range of parameters k and n. This linear-in-k dependence implies an exponential timegap between the plurality consensus process and the median process studied in [7]. 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. (2014). Simple Dynamics for Plurality Consensus. In 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'14) (pp.247-256). New York : ACM Press.
Simple Dynamics for Plurality Consensus
CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2014-01-01
Abstract
We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a color chosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors. The goal (of the agents) is to let the process converge to the stable configuration where all nodes support the plurality color. It is assumed that the initial color configuration has a sufficiently large bias s, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by an additive value s. 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 that each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly at random). We prove a tight bound on the convergence time which grows as ⊖(k log n) for a wide range of parameters k and n. This linear-in-k dependence implies an exponential timegap between the plurality consensus process and the median process studied in [7]. 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.File | Dimensione | Formato | |
---|---|---|---|
bcnpst_spaa14.pdf
solo utenti autorizzati
Licenza:
Copyright dell'editore
Dimensione
634.21 kB
Formato
Adobe PDF
|
634.21 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.