3-Majority with many colours reaches consensus (BCNPT16, Theorem 3.1; roadmap MAJ-12 (a)) #
Theorem 3.1 of Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many
opinions, SODA 2016, arXiv:1508.06782 (BCNPT16 below): from any configuration with
k ≤ n^{1/3 − ε} colours, 3-Majority reaches consensus within
O((k² √(log n) + k log n)(k + log n)) rounds w.h.p. The proof has two steps.
phase_colour_dies: fromj ≥ 2colours, one colour dies withinO(j² √(log n) + j log n)rounds with probability at least1/5(symmetry breaking, Lemma 3.3, then dropping, Lemmas 3.4 and 3.5, composed at the hitting time byhitProb_mul_le_event). The paper says1/4, the product of the probabilities1/2of Lemmas 3.3 and 3.5, ignoring the failure probability of Lemma 3.4.consensus_of_phases: if every phase ofLrounds removes a colour with probability at leastp, then afterMphases consensus fails with probability at most(1 − p/2)^M 2^k(the potential2^{#colours}).
consensus_many_opinions is Theorem 3.1 under the condition C k³ log n ≤ n, and
bcnpt16Phase2_of_pos is Theorem 3.1 as stated in the paper: it proves the hypothesis
Bcnpt16Phase2 ε of roadmap MAJ-6 (b), for every ε > 0, without changing it. Hence
threeMaj_anyStart_consensus_unconditional: Theorem 4 of Berenbrink, Clementi, Elsässer, Kling,
Mallmann-Trenn, Natale (PODC 2017) without hypothesis.
From a state where the symmetry is broken for j colours (BrokenSymmetry j), fewer than
j colours remain after the two dropping stages (t₃ rounds of Lemma 3.4, then t₄ rounds of
Lemma 3.5) with probability at least 2/5. The two stages are hypotheses here.
One phase (BCNPT16, proof of Theorem 3.1): there is C such that, from every
configuration c with j ≥ 2 colours and C j³ log n ≤ n, after any
t ≥ C (j² √(log n) + j log n) rounds fewer than j colours remain with probability at least
1/5.
Amplification over phases (BCNPT16, proof of Theorem 3.1): if from every configuration
with between 2 and k colours a phase of L rounds removes a colour with probability at least
p ≤ 1, then from a configuration c with at most k colours, consensus fails after M phases
with probability at most (1 − p/2)^M 2^k.
Consensus is absorbing, so missing it at time T implies missing it at every earlier
time T₀ ≤ T.
Theorem 3.1 (BCNPT16), under the condition C k³ log n ≤ n on the number k of colours:
there is C such that from every configuration c with k colours and C k³ log n ≤ n,
3-Majority has reached consensus after any T ≥ C (k² √(log n) + k log n)(k + log n) rounds with
probability at least 1 − 1/n.
The hypothesis Bcnpt16Phase2 of threeMaj_anyStart_consensus (roadmap MAJ-6 (b)), unfolded.
(Pinned, so that its definition is frozen together with bcnpt16Phase2_of_pos.)
Theorem 3.1 (BCNPT16, the adversary-free case), as stated in the paper: for every
ε > 0, from any configuration with k ≤ n^{1/3 − ε} colours, 3-Majority reaches consensus
within O((k² √(log n) + k log n)(k + log n)) rounds with probability at least 1 − 1/n. This is
the hypothesis Bcnpt16Phase2 ε of threeMaj_anyStart_consensus (roadmap MAJ-6 (b)).
Theorem 4 of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, Natale (PODC 2017),
without hypothesis: from any configuration of colours in [n], 3-Majority reaches consensus within
any T ≥ C n^{3/4} log^{7/8} n rounds with probability at least 1 − 2/n, for n ≥ N
(threeMaj_anyStart_consensus with its Phase 2 hypothesis discharged by Theorem 3.1 of BCNPT16
for ε = 1/24).