The Median Dynamics and 2-Choices
1 The model
This section, the four following ones and the one against an adaptive adversary formalize Doerr, Goldberg, Minder, Sauerwald and Scheideler, Stabilizing consensus with the power of two choices (SPAA 2011). Claim 2.9 of the paper, a hitting-time lemma, is formalized in the shared dynamics package, with two points made explicit there: the target \(c_4\log q\) is at most \(q\), and \(c_5\) also depends on \(c_1,c_2,c_3\) (details).
Values lie in a linear order. In a round every node samples two nodes uniformly at random (independently, with replacement) and adopts the median of its own value and the two sampled values. With two values this is 2-Choices: a node keeps its value unless both samples hold the other one.
2 Structure
The median commutes with monotone maps; hence for every threshold \(\theta \) the indicator of \(\{ x_v\ge \theta \} \) evolves, round by round and for the same samples, as the binary median process.
\(\mathrm{med}(a,b,c)=\max (\min (a,b),\min (\max (a,b),c))\), and monotone maps commute with \(\min \) and \(\max \).
Every new value is a current value, values stay within any interval containing all current values, consensus configurations are fixed, and consensus is reached almost surely.
The median is one of its arguments; the round in which every node samples node \(0\) twice gives consensus and has positive probability; conclude with the shared absorption theorem.
With two values and a fraction \(p\) of true, the expected number of true after one round is \(n(3p^2-2p^3)\), the same cubic as for 3-Majority.
A true node stays unless both samples are false, a false node switches iff both samples are true.
With two values, the median rule and 2-Choices are the same kernel, and its mean-field map (shared library) is the majority map \(p\mapsto 3p^2-2p^3\), the mean-field map of binary 3-Majority.
Theorem 4 divided by \(n\); with two colours the 2-Choices rule is the median of three Booleans.
The two dynamics share their mean-field map but not their chains: from two nodes, one holding true, one round leaves exactly one true with probability \(5/8\) under 2-Choices and \(1/2\) under 3-Majority.
3 Consensus from a vanishing bias
If \(\log n\ge 128\) and the true nodes outnumber the false ones by at least \(128\sqrt{n\log n}\), all nodes hold true after \(\lceil 128\log n\rceil \) rounds with probability at least \(1-128/n\).
Phases as in the plurality package: while it is small, the gap grows by a factor \(5/4\) per phase except with probability \(O(n^{-2})\) (Bernstein); then the minority shrinks by \(7/8\) per phase down to \(O(\log n)\); a final round reaches consensus except with probability \(O(n^{-1/2})\) (Markov). The phases are combined with the nested-phases lemma of the shared layer. The threshold \(\log n\ge 128\), i.e. \(n\ge e^{128}\), comes from these crude constants.
4 Consensus from any configuration
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\), from every binary configuration (possibly perfectly balanced) all nodes agree after \(\lceil C\log n\rceil \) rounds except with probability at most \(C/n\).
Take \(C=2^{18}\) and write \(g\) for the number of true nodes minus the number of false nodes. Escape: the potential \(e^{-|g|/(256\sqrt n)}\) contracts in expectation by \(e^{-1/65536}\) per round, up to an additive error \(e^{1/131072-\sqrt n/512}\): away from balance by Hoeffding’s lemma applied at every node, near balance because the next gap has variance at least \(n/10\), so by Paley–Zygmund it leaves \([-\sqrt n/4,\sqrt n/4]\) with probability at least \(9/64\). Iterating over \(\lceil 2^{17}\log n\rceil \) rounds and applying Markov’s inequality, \(|g|\ge 128\sqrt{n\log n}\) except with probability \(2/n\). Consensus: Theorem 6, applied to the configuration or to its flip, finishes within \(\lceil 128\log n\rceil \) rounds except with probability \(128/n\).
If every binary configuration fails to reach consensus within \(T\) rounds with probability at most \(\varepsilon \), then a configuration with \(m\) distinct values fails with probability at most \((m-1)\varepsilon \).
If a run has not reached consensus, two nodes hold values \(a{\lt}b\), and the threshold configuration \(\{ x_v\ge b\} \), which follows the same rounds by Theorem 2, has not reached consensus either. Take a union bound over the \(m-1\) thresholds above the minimum value.
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\), from every configuration with values in a linear order (any number of distinct values) all nodes agree after \(\lceil C\log n\rceil \) rounds except with probability at most \(C/n\). This is Theorem 1 of Doerr et al. without the adversary.
5 Many values: the middle one wins fast
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\), if the true nodes outnumber the false ones by at least \(\Delta \ge C\sqrt{n\log n}\), all nodes hold true after \(\lceil C(\log (n/\Delta )+\log \log n)\rceil \) rounds with probability at least \(1-C/n\).
Take \(C=128\) and chain one-round moves, each failing with probability at most \(n^{-2}\), through four segments: the gap grows by a factor \(5/4\) per round until the minority is below \(n/4\) (\(O(\log (n/\Delta ))\) rounds); six rounds bring the minority below \(n/8\); it then shrinks quadratically, \(m\mapsto \approx 3m^2/n\) (Bernstein), down to \(512\log n\) (\(O(\log \log n)\) rounds); eight more rounds give consensus. Consensus is absorbing, so the remaining rounds are harmless, and a union bound over the rounds gives the failure probability.
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\): if, for a value \(v\), the nodes holding a value \(\ge v\) outnumber those holding a value \({\lt}v\) by at least \(\Delta \ge C\sqrt{n\log n}\), and symmetrically the nodes holding a value \(\le v\) outnumber those holding a value \({\gt}v\) by at least \(\Delta \), then all nodes hold \(v\) after \(\lceil C(\log (n/\Delta )+\log \log n)\rceil \) rounds with probability at least \(1-2C/n\).
The indicators of \(\{ x_u\ge v\} \) and of \(\{ x_u\le v\} \) both evolve as 2-Choices with the same samples (the second because the median is self-dual), with gaps the two margins. When both reach consensus on true, all nodes hold \(v\); conclude with Theorem 10 (with the same \(C=128\)) and a union bound.
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\): if the nodes hold \(2k+1\) distinct values, each held by \(n/(2k+1)\) nodes, and \(C(2k+1)\sqrt{n\log n}\le n\), then the middle value is held by all nodes after \(\lceil C(\log (2k+1)+\log \log n)\rceil \) rounds with probability at least \(1-C/n\). This is the deterministic core of the odd case of Theorem 21 of Doerr et al.
Both margins around the middle value equal \(n/(2k+1)\ge C_0\sqrt{n\log n}\), and \(\log (n/\Delta )=\log (2k+1)\); apply Theorem 11 with \(C=2C_0\).
6 Two-sample voting on expanders
This section formalizes Theorem 4 of Cooper, Elsässer and Radzik, The power of two choices in distributed voting (ICALP 2014, arXiv:1404.7479); lemma numbers follow the arXiv version.
On a simple graph \(G\), in a round every vertex samples two neighbours independently and uniformly at random (with replacement) and adopts the median of its own opinion and the two sampled ones; with two opinions it adopts the sampled opinion when the two samples agree. For a majority opinion \(a\), the minority \(B\) is the set of vertices holding another opinion. \(E(S,T)\) is the number of ordered pairs \((u,v)\in S\times T\) of adjacent vertices, so \(E(S,S)=2|E(S)|\).
For a \(d\)-regular graph, \(\lambda _1\ge \lambda _2\ge \dots \ge \lambda _n\) are the eigenvalues of the transition matrix \(P=A/d\) and \(\lambda _G=\max \{ \lambda _2,|\lambda _n|\} \).
On every \(d\)-regular \(n\)-vertex graph and for all vertex sets \(S,T\), \(|E(S,T)-d|S||T|/n|\le \lambda _G\, d\sqrt{|S||T|}\).
Expand \(1_S\cdot P1_T=\sum _k\mu _k s_kt_k\) in an orthonormal eigenbasis. If \(\lambda _G{\lt}1\), every eigenvector other than the top one has eigenvalue at most \(\lambda _2{\lt}1\), hence is orthogonal to the all-ones vector, which is fixed by \(P\); so the top term is \(|S||T|/n\), and Cauchy–Schwarz bounds the others by \(\lambda _G\sqrt{|S||T|}\). If \(\lambda _G\ge 1\), both \(E(S,T)\) and \(d|S||T|/n\) lie in \([0,d\sqrt{|S||T|}]\).
If \(\lambda _G\le 3/5-\varepsilon \) and \(|S|\le \varepsilon n\), then \(E(S,S)\le (3/5)\, d|S|\).
By Lemma 15 with \(T=S\), \(E(S,S)\le d|S|^2/n+\lambda _Gd|S|\le (\varepsilon +3/5-\varepsilon )d|S|\).
If every superset \(S\supseteq B\) with \(|S|\le (1+1/\alpha )|B|\) spans at most \(\alpha d|S|\) edges, then after one round \(\mathbb E|B'|\le (1-(1-2\alpha )(1-3\alpha ))|B|=(24/25)|B|\), and \(|B'|\le (49/50)|B|\) with probability at least \(1-e^{-|B|/4850}\).
Let \(p_v\) be the fraction of neighbours of \(v\) in \(B\) and \(y=\sum _{v\in B}(1-p_v)\), which equals \(\sum _{v\notin B}p_v\) by double counting. Then \(\mathbb E|B'|=\sum _{v\notin B}p_v^2+\sum _{v\in B}(1-(1-p_v)^2)\). Cauchy–Schwarz gives \(\sum _{v\in B}(1-p_v)^2\ge y^2/|B|\). With \(C=\{ v\notin B:p_v{\gt}3/10\} \), the chord bound \(p^2\le (3/10)p+(p-3/10)^+\) and the sparsity of \(B\cup C\) (which has at most \((13/3)|B|\) vertices) give \(\sum _{v\notin B}p_v^2\le (3/10)y+(y-(2/5)|B|)/2\). Altogether \(\mathbb E|B'|\le (24/25)|B|-(y-(2/5)|B|)^2/|B|\). The new minority is a sum of independent indicators; the multiplicative Chernoff bound with mean bound \((24/25)m\) and \(\delta =1/48\) gives \(\Pr (|B'|\ge (49/50)m)\le e^{-m/4850}\) for every \(m\ge |B|\).
Let \(G\) be a \(d\)-regular \(n\)-vertex graph with \(d{\gt}0\) and \(\lambda _G\le 3/5-\varepsilon \), \(\varepsilon {\gt}0\), and let the minority have size at most \((\varepsilon /5)n\). After \(T\) rounds every vertex holds the majority opinion except with probability at most \((24/25)^T|B|+Te^{-\varepsilon n/24250}\). For \(T=\lceil C\log n\rceil \) with \(C=25000\) the failure probability is at most \(1/n+(C\log n+1)e^{-\varepsilon n/C}\), which tends to \(0\) for fixed \(\varepsilon \).
While \(|B|\le (\varepsilon /5)n\), every superset of \(B\) of size at most \((13/3)|B|\le \varepsilon n\) is sparse (Lemma 16), so by Lemma 17 the expected minority contracts by \(24/25\) in every round and one round leaves this region with probability at most \(e^{-\varepsilon n/24250}\) (take \(m=(\varepsilon /5)n\)). By induction on \(T\), a \([0,1]\)-valued observable bounded by the potential \(|B|\) in the region has expectation at most \((24/25)^T|B_0|+Te^{-\varepsilon n/24250}\); apply it to the indicator of not being in consensus. For the \(O(\log n)\) form, \((24/25)^T\le e^{-T/25}\le n^{-2}\) and \(|B_0|\le n\).
7 Two-sample voting from a small imbalance
This section formalizes Theorem 2 of Cooper, Elsässer and Radzik (ICALP 2014, arXiv:1404.7479), with its Phase I (Lemma 2 and Corollary 2), on top of Section 6; numbering follows the arXiv version (differences from the paper). Theorem 2 of the paper needs a major correction for very small \(\lambda _G\), and the corrected statement is formalized (Remark 27). Throughout, \(a\) is the majority opinion, \(A\) and \(B\) are the numbers of vertices holding \(a\) and not holding \(a\), \(n=A+B\), and primes denote the values after one round.
The imbalance is \(\nu =(A-B)/n\), and \(\eta =\alpha n/\sqrt{AB}\) for a parameter \(\alpha \). The flows of a round are \(\Delta _{BA}\), the number of vertices of \(B\) that hold \(a\) after the round, and \(\Delta _{AB}\), the number of vertices of \(A\) that no longer hold \(a\); so \(B'+\Delta _{BA}=B+\Delta _{AB}\). The length of Phase I is \(T_1(\nu ,c)=\left\lceil \log _{5/4}(1/(2\nu )) \right\rceil +\left\lceil \log _{4/3}(1/(4c)) \right\rceil \).
A \(d\)-regular graph satisfies the mixing hypothesis with parameters \(\alpha \) and \(c\) if \(|E(X,Y)-d|X||Y|/n|\le \alpha d\sqrt{|X||Y|}\) for all disjoint \(X,Y\) with \(|Y|\ge cn\) and \(|X|\ge (2/3)\alpha c^{3/2}n\).
If \(\lambda _G\le \alpha \), the mixing hypothesis holds with \(\alpha \) and every \(c\).
The expander mixing lemma (Lemma 15) with \(\lambda _G\le \alpha \).
In the next three lemmas, \(G\) is \(d\)-regular with \(d{\gt}0\), \(0{\lt}c\le 1/2\), \(0{\lt}\alpha \le c^{3/2}/36\), the mixing hypothesis holds with \(\alpha \) and \(c\), and \(cn\le B\le A\).
\(\mathbb {E}\Delta _{BA}\ge (A^2B/n^2)(1-2\eta )\) and \(\mathbb {E}\Delta _{AB}\le (AB^2/n^2)(1+15\eta )\).
Let \(p_v\) be the fraction of neighbours of \(v\) in \(B\). A vertex of \(B\) adopts \(a\) with probability \((1-p_v)^2\) and a vertex of \(A\) leaves \(a\) with probability \(p_v^2\), so \(\mathbb {E}\Delta _{BA}=\sum _{v\in B}(1-p_v)^2\) and \(\mathbb {E}\Delta _{AB}=\sum _{v\in A}p_v^2\). For the first, Cauchy–Schwarz gives \(\sum _{v\in B}(1-p_v)^2\ge (E(B,A)/d)^2/B\), and the mixing hypothesis gives \(E(B,A)\ge (dAB/n)(1-\eta )\). For the second, the hypothesis bounds the size of \(\{ v\in A:p_v\ge (1+2^j\eta )B/n\} \) by \(A/4^j\); summing \(p_v^2\) as a layer cake over these sets, up to the \(m\) with \(4^m\le n^2/(\eta B^2){\lt}4^{m+1}\), gives the bound, since \((1+3m)\eta \le 5\).
\(\Pr (\Delta _{BA}\le (A^2B/n^2)(1-3\eta ))\le e^{-\alpha ^2cn/6}\) and \(\Pr (\Delta _{AB}\ge (AB^2/n^2)(1+17\eta ))\le e^{-\alpha ^2c^2n/2}\).
Both flows are sums of independent indicators over the vertices of \(B\) and of \(A\). Apply the multiplicative Chernoff bounds with the lower and upper bounds on the means of Lemma 22, and \(\eta \ge 2\alpha \).
With probability at least \(1-e^{-\alpha ^2cn/6}-e^{-\alpha ^2c^2n/2}\), \(\nu '\ge \nu +\nu (1-\nu ^2)/2-12\alpha /\sqrt{1-\nu ^2}\). Any such \(\nu '\) satisfies \(\nu '\ge (5/4)\nu \) if \(120\alpha \le \nu \le 1/2\), and \(1-\nu '\le (3/4)(1-\nu )\) if \(1/2\le \nu \le 1-2c\).
\(\nu '-\nu =2(\Delta _{BA}-\Delta _{AB})/n\). Outside the two events of Lemma 23, \(\Delta _{BA}-\Delta _{AB}\ge AB(A-B)/n^2-\eta (3A^2B+17AB^2)/n^2\); with \(A=n(1+\nu )/2\) and \(B=n(1-\nu )/2\) this is the bound (the paper’s (ncnwd-Appx)). The two growth statements are elementary inequalities.
Let \(G\) be \(d\)-regular with \(d{\gt}0\), \(0{\lt}c\le 1/2\) and \(0{\lt}\alpha \le c^{3/2}/36\), and let the mixing hypothesis hold with \(\alpha \) and \(c\) (for instance \(\lambda _G\le \alpha \)). If \(\nu _0\ge 120\alpha \), then at some time \(t\le T_1=T_1(\nu _0,c)\) the minority has at most \(cn\) vertices, except with probability at most \(T_1(e^{-\alpha ^2cn/6}+e^{-\alpha ^2c^2n/2})\).
Freeze the process at the first time the minority has at most \(cn\) vertices. While it is not frozen, \(B\ge cn\) and \(\nu \le 1-2c\), and by Lemma 24 the imbalance stays above the deterministic envelope \((5/4)^t\nu _0\) up to \(1/2\), then \(1-(3/4)^{t-t_1}/2\), except with probability \(e^{-\alpha ^2cn/6}+e^{-\alpha ^2c^2n/2}\) per round. After \(T_1\) rounds the envelope exceeds \(1-2c\), so the process is frozen; a union bound over the rounds gives the claim. With \(\lambda _G\le \alpha \), Lemma 21 gives the mixing hypothesis.
Let \(G\) be \(d\)-regular with \(d{\gt}0\) and \(\nu _0{\gt}0\), \(4000\lambda _G\le \nu _0\), and let \(\alpha =\nu _0/4000\) and \(T_1=T_1(\nu _0,1/20)\). For every \(T_2\), after \(T_1+T_2\) rounds every vertex holds \(a\), except with probability at most \(T_1(e^{-\alpha ^2n/120}+e^{-\alpha ^2n/800})+(24/25)^{T_2}n+(T_1+T_2)e^{-n/97000}\). Hence there are absolute constants \(K,C{\gt}0\) (\(K=4000\), \(C=2\cdot 10^{10}\)) such that, if \(K\lambda _G\le \nu _0\), after \(\left\lceil C\log n \right\rceil \) rounds every vertex holds \(a\) except with probability at most \(1/n+(2C\log n+C)e^{-\nu _0^2n/C}\).
Phase I (Theorem 25 with \(c=1/20\) and \(\alpha =\nu _0/4000\ge \lambda _G\); note \(\alpha \le c^{3/2}/36\) and \(120\alpha \le \nu _0\)) brings the minority to at most \(n/20\) at some time \(t\le T_1\). From then on, Theorem 4 (Theorem 18 with \(\varepsilon =1/4\), which applies since \(\lambda _G\le 1/4000\le 3/5-1/4\)) finishes; the composition at the random time \(t\) is an induction on the length of Phase I. For the \(O(\log n)\) form, \(T_1\le 5\log n+7\) (as \(\nu _0\ge 1/n\)), and the remaining rounds make \((24/25)^{T_2}n\le 1/n\).
The paper states Theorem 2 with success probability \(1-o(1)\) whenever \(\nu _0\ge K\lambda _G\), on every \(d\)-regular graph. Its proof applies Lemma 2 with \(\alpha =\lambda _G\), whose failure probability is \(e^{-\Theta (\lambda _G^2n)}\); this is not \(o(1)\) when \(\lambda _G\) is of order \(1/\sqrt n\) or smaller. On the complete graph, \(\lambda _G=1/(n-1)\), so a constant difference \(A-B\in \{ K+2,K+3\} \) satisfies the hypothesis for \(n\ge K+3\); the first round produces fluctuations of order \(\sqrt n\) in \(A-B\), and by symmetry the initial majority then wins with probability tending to \(1/2\). Theorem 26 is the corrected statement: it keeps the hypothesis \(\nu _0\ge K\lambda _G\) and bounds the failure probability in terms of \(\nu _0^2n\), which tends to \(0\) once \(\nu _0^2n\) is large compared with \(\log \log n\) (details).
8 Almost stable consensus against an adaptive adversary
An adversary maps the list of rounds played so far (the current one last) and the output of the median rule in the current round to a new configuration; it is \(F\)-bounded if it recolours at most \(F\) nodes, and it uses values of \(S\) if every value it writes lies in \(S\). The run against the adversary applies, in every round, the median rule and then the adversary. More generally, a perturbed run is any function of the rounds played so far that starts at \(x\) and, after every round, differs from the output of the median rule in at most \(F\) nodes. A configuration is in almost consensus on \(b\) with \(K\) exceptions if at most \(K\) nodes hold a value other than \(b\); almost stable consensus during the times \(T_0,\dots ,T_0+H\) means almost consensus on the same value \(b\) at all these times.
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\) and \(CF\le \sqrt n\), for every binary configuration, every perturbed run with budget \(F\) (in particular, the run against every \(F\)-bounded adversary) and every \(H\ge 0\), almost stable consensus with \(C(F+\log n)\) exceptions holds during the times \(\lceil C\log n\rceil ,\dots ,\lceil C\log n\rceil +H\), except with probability at most \((C\log n+H)/n^2\). This is the two-value case (Theorem 10 of the 2009 version) of the main theorem of Doerr et al.
Take \(C=2^{20}\), so \(F\le \sqrt n/1024\), and let \(g\) be the gap and \(K=\max (16F,1024\log n)\). Recolouring \(F\) nodes moves \(g\) by at most \(2F\) and the minority by at most \(F\). Escape: the potential \(e^{-|g|/(256\sqrt n)}\) of Theorem 7 grows by at most \(e^{1/131072}\) under the recolourings, so it still contracts by \(e^{-1/131072}\) per round up to an additive \(e^{1/65536-\sqrt n/512}\); after \(\lceil 2^{19}\log n\rceil \) rounds Markov’s inequality gives \(|g|\ge 128\sqrt{n\log n}\) except with probability \(2/n^2\). Growth and saturation (for \(g{\gt}0\); otherwise flip): a chain of one-round moves, each failing with probability at most \(n^{-2}\) for every recolouring, along sets indexed by time: the gap grows from \(G\) to \(\min (9G/8,17n/32)\) (Hoeffding: \(5G/4\) before the recolouring), then the minority shrinks from \(t\) to \(\max (15t/16,K)\) (Bernstein: \(\max (7t/8,512\log n)\) before the recolouring) and stays below \(K\). A union bound over the rounds of the chain and of the window gives the bound.
There is a constant \(C{\gt}0\) such that, whenever \(\log n\ge C\) and \(CF\le \sqrt n\): let \(S\) be a set of \(m\) legal values containing the values of a configuration \(x\). Against every \(F\)-bounded adversary that only writes values of \(S\), and for every \(H\ge 0\), almost stable consensus with \(C(F+\log n)\) exceptions holds during the times \(\lceil C\log n\rceil ,\dots ,\lceil C\log n\rceil +H\), except with probability at most \((m-1)(C\log n+H)/n^2\).
Take \(C=2^{20}\). All values of the run lie in \(S\). For every legal value \(b\), the threshold \(u\mapsto [b\le x_u]\) of the run is a perturbed run of 2-Choices with the same budget, because the median commutes with monotone maps and thresholding does not increase the Hamming distance. If, for every legal \(b\) above the minimum \(m_0\), the threshold run stays in almost consensus on some \(c_b\) with \(K\) exceptions, let \(w\) be the largest legal value with \(w=m_0\) or \(c_w=\texttt{true}\): the nodes below \(w\) are exceptions of the threshold at \(w\), and the nodes above \(w\) are exceptions of the threshold at the next legal value, so the run is in almost consensus on \(w\) with \(2K\) exceptions. Conclude with the internal bound of Theorem 29 and a union bound over the \(m-1\) thresholds.
9 Plurality consensus with \(k\) colours
This section formalizes the synchronous upper bound of Elsässer, Friedetzky, Kaaser, Mallmann-Trenn and Trinker, arXiv:1602.04667 (arXiv v5 numbering, v5 being titled Rapid asynchronous plurality consensus): Theorem 1.2 and Section 2.1, without the adversary and without the hypothesis \(k=O(n^\varepsilon )\) (differences from the paper). Throughout, \(c_i\) is the number of nodes of colour \(i\), primes denote the values after one round, and \(S=\sum _j c_j^2\).
Colours lie in any type with decidable equality. In a round every node samples two nodes uniformly at random (independently, with replacement) and adopts their colour if the two samples hold the same colour; otherwise it keeps its own. \(c_i\) is the number of nodes of colour \(i\), and the number of nodes whose two samples both hold \(i\) is denoted \(\mathrm{twice}_i\).
Consensus configurations are fixed; \(c_i'\le c_i+\mathrm{twice}_i\), so an extinct colour stays extinct. On two colours the rule is the median of the own colour and the two samples. For the same rounds, every node that holds true in the binary median process started from the indicator of colour \(i\) holds colour \(i\).
A node that does not hold \(i\) adopts \(i\) only if both samples hold \(i\). With two colours, the new colour is the majority among the own colour and the two samples, that is, their median. For the domination, the indicator of \(\{ \text{new colour}=i\} \) is at least the median of the three indicators, and the median is monotone; induct on the rounds.
\(\mathbb {E}c_i'=c_i(1+c_i/n-S/n^2)\); hence \(c_r\le c_s\) implies \(\mathbb {E}c_r'\le \mathbb {E}c_s'\) (Observation 2.1), and \(\mathbb {E}(c_i'-c_j')=(c_i-c_j)(1+(c_i+c_j)/n-S/n^2)\). If every colour other than \(i\) has at most \(b\) nodes, then \(S\le c_i^2+(n-c_i)b\). If \(a\) and \(b\) are the sizes of the largest and the second largest colour, then \(\mathbb {E}(a'-b')\ge (a-b)(1+(a/n)(1-a/n))\).
A node ends in colour \(i\) with probability \((c_i/n)^2+[x_v=i](1-S/n^2)\); sum over the nodes. The map \(c\mapsto c(1+c/n-S/n^2)\) is increasing on \(c\ge 0\) since \(S\le n^2\). The aggregation bound is \(\sum _{j\ne i}c_j^2\le b\sum _{j\ne i}c_j=b(n-c_i)\), and with \(S\le a^2+nb\) the gap formula gives the last bound.
Let colour \(i\) be a largest colour, with \(a=c_i{\gt}0\) nodes, and \(j\ne i\). For every \(\lambda \ge 0\), \(\Pr (a'-c_j'\le \mathbb {E}(a'-c_j')-\lambda )\le \exp (-\lambda ^2/(20a^2/n+4\lambda /3))\) and \(\Pr (a'\le \mathbb {E}a'-\lambda )\le \exp (-\lambda ^2/(4a^2/n+2\lambda /3))\). In particular, if \(128\sqrt{n\log n}\le g\le a\), both probabilities are at most \(n^{-12}\) for \(\lambda =ga/(8n)\) and \(\lambda =ag/(4n)\) respectively.
Both quantities are sums of independent per-node contributions bounded by \(1\) in absolute value. A node of colour \(i\) or \(j\) contributes only when it leaves its colour, which has probability at most \(S/n^2\le a/n\), and any other node joins \(i\) or \(j\) with probability at most \(2a^2/n^2\). Bounding each variance by the second moment about the node’s current contribution gives \(\mathrm{Var}(a'-c_j')\le 10a^2/n\) and \(\mathrm{Var}(a')\le 2a^2/n\); apply Bernstein’s inequality. The exponents are then at least \((g^2/(1344n))\ge 12\log n\).
There are constants \(z,C{\gt}0\) such that, whenever \(\log n\ge C\): if colour \(i\) is the largest, with \(a=c_i\le n/2\) nodes, \(j\) is the second largest, with \(b=c_j\) nodes, and \(a-b\ge z\sqrt{n\log n}\), then \(a'-b'{\gt}(a-b)(1+a/(4n))\) with probability at least \(1-C/n^2\).
If \(c_c\le c_b\), then \(\Pr (c_c'\ge t)\le \Pr (c_b'\ge t)\) for every \(t\).
Choose a permutation \(\tau \) of the nodes sending every node of colour \(c\) to a node of colour \(b\). For every node \(v\), the sample pairs that make \(v\) end in colour \(c\) are at most as many as those that make \(\tau (v)\) end in colour \(b\): a node of another colour adopts a colour of size \(m\) on the \(m^2\) pairs with both samples on it, a node of that colour keeps it on the \(n^2-S+m^2\) pairs that do not agree on another colour, and both counts increase with \(m\). Choose a permutation of the sample pairs embedding the first set into the second. The induced bijection of rounds preserves the uniform distribution and maps the rounds with \(c_c'\ge t\) into the rounds with \(c_b'\ge t\). The paper’s coupling, read literally, needs a minor correction (details).
There are constants \(z,C{\gt}0\) such that, whenever \(\log n\ge C\): if colour \(i\) has \(a=c_i\le 3n/4\) nodes and leads every other colour by at least \(g\ge z\sqrt{n\log n}\), then with probability at least \(1-C/n^2\) after one round \(a'\ge a\) and colour \(i\) leads every other colour by at least \(g(1+a/(8n))\).
Take \(z=128\) and \(C=2\), and let \(b\) be the second largest colour. For every other colour \(j\), Observation 2.1 gives \(\mathbb {E}c_j'\le \mathbb {E}b'\), so by Lemma 33 \(\mathbb {E}(a'-c_j')\ge (a-b)(1+(a/n)(1-a/n))\ge g(1+a/(4n))\) since \(a\le 3n/4\). Lemma 34 with \(\lambda =ga/(8n)\) bounds the failure for \(j\) by \(n^{-12}\). The aggregation bound gives \(\mathbb {E}a'-a\ge ag/(4n)\), so \(a'{\lt}a\) has probability at most \(n^{-12}\). A union bound over the at most \(n\) colours present gives the failure probability \(2/n^2\). This replaces the coupling of Lemma 2.3, and the range \(a\le 3n/4\) (instead of \(n/2\)) closes the gap before the two-colour phase.
There are constants \(z,C{\gt}0\) such that, whenever \(\log n\ge C\): if colour \(i\) leads every other colour by at least \(z\sqrt{n\log n}\), then after \(\lceil C(n/c_i)\log n\rceil \) rounds it holds at least \(3n/4\) nodes with probability at least \(1-C/n\).
Take \(z=C=128\), \(a_0=c_i\), \(g_0\) the initial lead and \(q=1+a_0/(8n)\). Consider the moving targets “colour \(i\) holds \(3n/4\) nodes, or it holds at least \(a_0\) nodes and leads every other colour by \(g_0q^t\)”. Each round leaves them with probability at most \(2/n^2\), by Lemma 37 while \(a\le 3n/4\), and because a colour holding \(3n/4\) nodes keeps them except with probability \(n^{-2}\) (Bernstein, drift from the aggregation bound). Since \(q^{\lceil 128(n/a_0)\log n\rceil }{\gt}n\), a lead of \(g_0q^t\) is impossible at the end, so the colour holds \(3n/4\) nodes.
If \(\log n\ge 128\) and colour \(i\) holds at least \(3n/4\) nodes, all nodes hold \(i\) after \(\lceil 128\log n\rceil \) rounds with probability at least \(1-128/n\).
There are constants \(z,C{\gt}0\) such that, whenever \(\log n\ge C\), for every number \(k\) of colours: if colour \(i\) leads every other colour by at least \(z\sqrt{n\log n}\), all nodes hold \(i\) after \(\lceil C(n/c_i)\log n\rceil \) rounds, and hence after \(\lceil Ck\log n\rceil \) rounds, with probability at least \(1-C/n\).
Take \(z=128\) and \(C=384\): Lemma 38, then Lemma 39 from the configuration reached, with failure at most \(256/n\); consensus is absorbing, so more rounds do not hurt. For the second form, \(c_i\ge n/k\). The paper’s proof of Theorem 1.2 needs a minor correction (the range \(n/2{\lt}a{\lt}(1/2+\varepsilon _1)n\) and the time bound), which Lemma 37 supplies.
With two colours, a gap of \(C\sqrt{n\log n}\) gives consensus on the majority after \(\lceil C\log n\rceil \) rounds with probability at least \(1-C/n\), whenever \(\log n\ge C\). With finitely many colours, consensus is reached almost surely.
10 A lower bound for 2-Choices
This section formalizes the 2-Choices lower bound of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn and Natale, Ignore or comply? On breaking symmetry in consensus (PODC 2017): Theorem 5 of arXiv:1702.04921 (v1) and the 2-Choices half of its Theorem 1 (Simplified) (differences from the paper).
The number of nodes that see colour \(i\) twice is a sum of \(n\) independent Bernoulli variables of parameter \((c_i/n)^2\), so \(\mathbb {E}e^{\theta \, \mathrm{twice}_i}=(1+(c_i/n)^2(e^\theta -1))^n\). The expected number of nodes whose two samples hold different colours is \(n-S/n\), and if every colour has at most \(\ell \) nodes, the expected number of nodes that change colour is at most \(\ell \).
The samples of different nodes are independent. Two samples hold the same colour with probability \(S/n^2\), and only such nodes can change colour; \(S\le \ell n\).
If \(c_i\le L\), then for every \(T\), the probability that \(c_i(t){\gt}L\) for some \(t\le T\) is at most \(\exp (-(L-c_i)+(e-1)TL^2/n)\).
Induction on the horizon. While \(c_i\le L\), \(c_i'\le c_i+\mathrm{twice}_i\) (Lemma 32) and, with \(\theta =1\), \(\mathbb {E}e^{\mathrm{twice}_i}\le \exp ((e-1)n(c_i/n)^2)\le \exp ((e-1)L^2/n)\), so \(e^{c_i(t)-(e-1)tL^2/n}\), stopped when \(c_i\) exceeds \(L\), is a supermartingale; conclude with Markov’s inequality. This replaces the paper’s domination by a process with binomial increments.
There is a constant \(\gamma _0\) such that for every \(\gamma \ge \gamma _0\): if every colour has at most \(\ell \) nodes, \(\ell '=\max \{ 2\ell ,\gamma \log n\} \) and \(T{\lt}n/(\gamma \ell ')\), the probability that some colour has more than \(\ell '\) nodes at some time \(t\le T\) is at most \(1/n\).
Take \(\gamma _0=8\). By Lemma 43 with \(L=\ell '\), since \(L-c_i\ge \ell '/2\) and \(T\ell '^2/n{\lt}\ell '/\gamma \), one colour exceeds \(\ell '\) with probability at most \(\exp (-\ell '(1/2-(e-1)/\gamma ))\le n^{-2}\); take a union bound over the at most \(n\) colours present. A constant in the paper’s proof needs a minor correction (\(\gamma \ge 36\) instead of \(\gamma \ge 18\) in its Chernoff step); the theorem is unaffected.
For every \(\beta {\gt}0\) there is \(C{\gt}0\) such that, from every configuration in which every colour has at most \(\beta \log n\) nodes, 2-Choices reaches consensus at some time \(t\le T\) with probability at most \(1/n\), for every \(T\) with \((T+1)C\log n{\lt}n\).
Take \(\gamma =\max \{ 8,2\beta \} \) and \(C=\gamma ^2\). Then \(\ell '=\gamma \log n\), the window of Theorem 44 contains \(T\), and consensus would put \(n{\gt}\ell '\) nodes on one colour.