3-Majority from any configuration (BCEKMN17, Theorem 4; roadmap MAJ-6, part (b)) #
Theorem 4 of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, Natale (PODC 2017,
arXiv:1702.04921): from any configuration, 3-Majority reaches consensus w.h.p. within
O(n^{3/4} log^{7/8} n) rounds. The proof has two phases.
- Phase 1 (
threeMaj_reduce_whp): from up toncolours tokcolours within24 (n/k) log nrounds w.p.≥ 1 − 1/n, by Lemma 2 (3-Majority is at least as fast as Voter) and Lemma 3 (the Voter bound). It is used withk ≈ n^{1/4} log^{1/8} n. - Phase 2: from
k ≤ n^{1/3−ε}colours to consensus, the paper cites Theorem 3.1 of Becchetti, Clementi, Natale, Pasquale, Trevisan (Stabilizing consensus with many opinions, SODA 2016), restated as Theorem 8 of BCEKMN17. That result is not part of this paper:Bcnpt16Phase2 εstates it for oneε, and the bridge theoremthreeMaj_anyStart_consensustakes it as a hypothesis, exactly as the paper's proof does. It is formalized inManyOpinions*.lean(roadmap MAJ-12 (a)):bcnpt16Phase2_of_posprovesBcnpt16Phase2 εfor everyε > 0, andthreeMaj_anyStart_consensus_unconditionalis Theorem 4 without hypothesis.
Phase 1 of Theorem 4 (BCEKMN17, Section 3, from Lemmas 2 and 3): from any configuration,
3-Majority has at most k colours after any T ≥ 24 (n/k) log n rounds, with probability at
least 1 − 1/n.
Theorem 8 of BCEKMN17 (Theorem 3.1 of Becchetti, Clementi, Natale, Pasquale, Trevisan,
SODA 2016), for one ε, as a hypothesis: there are constants C, N such that for n ≥ N, from
any configuration of colours in [n] with k ≤ n^{1/3 − ε} colours, 3-Majority reaches
consensus within any T ≥ C (k² log^{1/2} n + k log n)(k + log n) rounds, with probability at
least 1 − 1/n. It holds for every ε > 0 (bcnpt16Phase2_of_pos, in
ManyOpinionsMain.lean).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Theorem 4 (BCEKMN17): 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. The cited Phase 2 result (Theorem 8, for ε = 1/24) is a hypothesis here;
threeMaj_anyStart_consensus_unconditional (in ManyOpinionsMain.lean) discharges it.