The Median Dynamics and 2-Choices
1 The model
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\).