The Median Dynamics and 2-Choices
1 The model
This section, the four following ones and the last 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.
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 5, 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 9 (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 10 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 14 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 15), so by Lemma 16 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 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 6 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 19 and a union bound over the \(m-1\) thresholds.