Documentation

ThreeMajority.ManyOpinionsMain

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.

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.

theorem ThreeMajority.two_fifths_le_event_of_broken {n : ℕ} [NeZero n] {j t₃ t₄ : ℕ} {C₃ : ℝ} (hst1 : ∀ (x : Fin n → Fin n) (a : Fin n), numColours x ≤ j → ↑(colourCount x a) ≤ ↑n / ↑j - 16 * √(↑j * ↑n * Real.log ↑n) → (expList (Tgt3 n) t₃ fun (l : List (Tgt3 n)) => if C₃ * ↑j ^ 2 * Real.log ↑n < ↑(colourCount (runCol x l) a) then 1 else 0) ≤ 1 / ↑n) (hst2 : ∀ (x : Fin n → Fin n) (a : Fin n), numColours x ≤ j → ↑(colourCount x a) ≤ ↑n / (2 * ↑j) → 1 / 2 ≤ expList (Tgt3 n) t₄ fun (l : List (Tgt3 n)) => if colourCount (runCol x l) a = 0 then 1 else 0) (hthr : C₃ * ↑j ^ 2 * Real.log ↑n ≤ ↑n / (2 * ↑j)) (hn5 : 5 ≤ ↑n) (b : Fin n → Fin n) (hb : BrokenSymmetry j b) :
2 / 5 ≤ (Dynamics.Kernel.ofStep stepCol).event (fun (y : Fin n → Fin n) => numColours y < j) (t₃ + t₄) b

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.

theorem ThreeMajority.phase_colour_dies :
∃ (C : ℝ), ∀ (n : ℕ) (c : Fin n → Fin n), 2 ≤ numColours c → C * ↑(numColours c) ^ 3 * Real.log ↑n ≤ ↑n → ∀ (t : ℕ), C * (↑(numColours c) ^ 2 * √(Real.log ↑n) + ↑(numColours c) * Real.log ↑n) ≤ ↑t → 1 / 5 ≤ expList (Tgt3 n) t fun (l : List (Tgt3 n)) => if numColours (runCol c l) < numColours c then 1 else 0

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.

theorem ThreeMajority.consensus_of_phases {n : ℕ} (L k M : ℕ) {p : ℝ} (hp : p ≤ 1) (hphase : ∀ (x : Fin n → Fin n), 2 ≤ numColours x → numColours x ≤ k → p ≤ expList (Tgt3 n) L fun (l : List (Tgt3 n)) => if numColours (runCol x l) < numColours x then 1 else 0) (c : Fin n → Fin n) (hc : numColours c ≤ k) :
(expList (Tgt3 n) (M * L) fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 1) ≤ (1 - p / 2) ^ M * 2 ^ k

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.

theorem ThreeMajority.expList_not_consensus_le {n : ℕ} [NeZero n] {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) {T₀ T : ℕ} (h : T₀ ≤ T) :
(expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 1) ≤ expList (Tgt3 n) T₀ fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 1

Consensus is absorbing, so missing it at time T implies missing it at every earlier time T₀ ≤ T.

theorem ThreeMajority.nine_tenths_pow_mul_two_pow_le {n : ℕ} (hn : 1 ≤ n) (k : ℕ) :
(9 / 10) ^ (10 * (k + ⌈Real.log ↑n⌉₊)) * 2 ^ k ≤ 1 / ↑n

The number of phases: with M = 10 (k + ⌈log n⌉), (9/10)^M 2^k ≤ 1/n (since (9/10)^10 ≤ e^{-1} and 2 ≤ e).

theorem ThreeMajority.consensus_many_opinions :
∃ (C : ℝ), ∀ (n : ℕ) (c : Fin n → Fin n), C * ↑(numColours c) ^ 3 * Real.log ↑n ≤ ↑n → ∀ (T : ℕ), C * ((↑(numColours c) ^ 2 * √(Real.log ↑n) + ↑(numColours c) * Real.log ↑n) * (↑(numColours c) + Real.log ↑n)) ≤ ↑T → (expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 1) ≤ 1 / ↑n

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.

theorem ThreeMajority.bcnpt16Phase2_iff (ε : ℝ) :
Bcnpt16Phase2 ε ↔ ∃ (C : ℝ) (N : ℝ), ∀ (n : ℕ), N ≤ ↑n → ∀ (c : Fin n → Fin n), ↑(numColours c) ≤ ↑n ^ (1 / 3 - ε) → ∀ (T : ℕ), C * ((↑(numColours c) ^ 2 * √(Real.log ↑n) + ↑(numColours c) * Real.log ↑n) * (↑(numColours c) + Real.log ↑n)) ≤ ↑T → (expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 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 ThreeMajority.bcnpt16Phase2_of_pos {ε : ℝ} (hε : 0 < ε) :

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 ThreeMajority.threeMaj_anyStart_consensus_unconditional :
∃ (C : ℝ) (N : ℝ), ∀ (n : ℕ), N ≤ ↑n → ∀ (c : Fin n → Fin n) (T : ℕ), C * ↑n ^ (3 / 4) * Real.log ↑n ^ (7 / 8) ≤ ↑T → (expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 1) ≤ 2 / ↑n

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).