Simple dynamics for plurality consensus

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 bias s 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 \(\mathcal {O}( \min \{ k, (n/\log n)^{1/3} \} \, \log n )\) with high probability, provided that \(s \geqslant c \sqrt{ \min \{ 2k, (n/\log n)^{1/3} \}\, n \log n}\). We then prove that our upper bound above is tight as long as \(k \leqslant (n/\log n)^{1/4}\). 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.

1. We say that a family of events \(\{\mathcal {E}_n\}_n\) holds w.h.p. if a positive constant c exists such that \(\mathbf {P}\left( \mathcal {E}_n \right) \geqslant 1 - n^{-c}\) for sufficiently large n.

2. In the (simple) consensus problem the goal is to reach any stable monochromatic configuration (any color is accepted) starting from any initial configuration.

3. We are using the fact that \(\mathbf {P}\left( A\cap B \right) \geqslant 1-\mathbf {P}\left( A^{C} \right) -\mathbf {P}\left( B^{C} \right) \).

4. Notice that the inequality holds in particular for negative a as well.

5. See e.g., Chapter 17 in [15] for a summary of martingales and related results.

6. A number of pretty similar “folklore” results can be found in specialized mathematical forums, for example http://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound.

Authors and Affiliations

1. Sapienza Università di Roma, Rome, Italy

   Luca Becchetti

2. Max Planck Institute for Informatics, Saarbrücken, Germany

   Emanuele Natale

3. Università Tor Vergata di Roma, Rome, Italy

   Andrea Clementi & Francesco Pasquale

4. Rome, Italy

   Riccardo Silvestri

5. UC Berkeley, Berkeley, CA, USA

   Luca Trevisan

Corresponding author

Correspondence to Andrea Clementi.

Partially supported by Italian MIUR-PRIN 2010–2011 Project ARS TechnoMedia, the EU FET Project MULTIPLEX 317532, and by the National Science Foundation under Grants No. CCF 1540685 and CCF 1655215. A preliminary version of this paper appeared in the Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’14).

Useful bounds

Lemma 11

(Chernoff bounds) Let \(X = \sum _{i=1}^n X_i\) where \(X_i\)’s are independent Bernoulli random variables and let \(\mu = \mathbf {E}_{} \left[ X \right] \). Then,

1. 1.

   For any \(0 < \delta \leqslant 4\), \(\mathbf {P}\left( X > (1 + \delta )\mu \right) < e^{-\frac{\delta ^2\mu }{4}}\);

2. 2.

   For any \(\delta \geqslant 4\), \(\mathbf {P}\left( X > (1 + \delta )\mu \right) < e^{-\delta \mu }\);

3. 3.

   For any \(\lambda > 0\), \(\mathbf {P}_{} \left( X \geqslant \mu + \lambda \right) \leqslant e^{-2 \lambda ^2 / n}\).

Lemma 12

(Jensen inequality) Let \(\phi \,:\, \mathbb {R} \rightarrow \mathbb {R}\) be a convex function and \(x_1, \ldots , x_k \in \mathbb {R}\) be k real numbers, then

In Sect. 4.4, we use the following “reverse”-Chernoff bound [19, Theorem 2]^{Footnote 6}

Theorem 5

(Reverse Chernoff bound) Let X be the sum of m independent Bernoulli variables with probability \(p\leqslant {1} / {4}\) and let \(\mu = pm\). Then, for any \(t \in ( 0, m-\mu )\):

Reprints and permissions