- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
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.
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 \).
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|\} \).
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.
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\).
\(\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 )\).
\(\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}\).
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\).
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}\).
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\).
- Median.TwoChoices.step_of_ne
- Median.TwoChoices.step_of_eq
- Median.TwoChoices.step_of_consensus
- Median.TwoChoices.count_step_le
- Median.TwoChoices.count_step_eq_zero
- Median.TwoChoices.rule_bool
- Median.TwoChoices.step_bool
- Median.TwoChoices.run_bool
- Median.TwoChoices.count_true
- Median.TwoChoices.run_dominates
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.
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\).
\(\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))\).
- Median.TwoChoices.avg_pair
- Median.TwoChoices.avg_step_node
- Median.TwoChoices.expected_count
- Median.TwoChoices.expected_count_mul
- Median.TwoChoices.sum_count
- Median.TwoChoices.expected_count_mono
- Median.TwoChoices.expected_gap
- Median.TwoChoices.sum_sq_le_aggregate
- Median.TwoChoices.sum_sq_le_max
- Median.TwoChoices.expected_gap_ge
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 \).
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\): 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\).
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))\).
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.
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.
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.
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\).
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})\).
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}\).
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 \).
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.
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\).
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\).
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.
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\).
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\).
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\).
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.
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.
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\).