Documentation

RumorSpread.Main

Main theorem: push informs the complete graph in O(log n) rounds w.h.p. #

prNotAllInformed n v₀ T is the probability that after T rounds of the uniform push protocol on K_n, started from the single informed node v₀, some node is still uninformed. The main theorem states that for T = ⌈117 log n⌉ + 23 + ⌈6 log n⌉ = O(log n) this probability is ≤ 2/n.

The constants are deliberately crude (the sharp threshold is log₂ n + ln n): they are chosen so that the verification needs only log 2 < 0.694 and the bound 1 - 1/x ≤ log x.

noncomputable def RumorPush.prNotAllInformed (n : ℕ) (v₀ : Fin n) (T : ℕ) :

Probability that not all nodes are informed after T rounds, starting from the single informed node v₀.

Equations
Instances For
    theorem RumorPush.prNotAllInformed_le {n : ℕ} (hn : 2 ≤ n) (v₀ : Fin n) (L T₁ T₂ : ℕ) (hL : ↑n ≤ (9 / 8) ^ L) :
    prNotAllInformed n v₀ (T₁ + T₂) ≤ 2 ^ L * (15 / 16) ^ T₁ + (2 / 3) ^ T₂ * ↑n

    Gluing the two phases: failure requires either phase 1 to fail (informed set still ≤ n/2 after T₁ rounds) or phase 2 to leave an uninformed node (controlled by Markov via the expected uninformed count).

    theorem RumorPush.numeric_A {n : ℕ} (hn : 2 ≤ n) :
    ↑n ≤ (9 / 8) ^ (⌈9 * Real.log ↑n⌉₊ + 1)

    The choice L = ⌈9 log n⌉ + 1 makes (9/8)^L ≥ n.

    theorem RumorPush.numeric_B {n : ℕ} (hn : 2 ≤ n) :
    2 ^ (⌈9 * Real.log ↑n⌉₊ + 1) * (15 / 16) ^ (⌈117 * Real.log ↑n⌉₊ + 23) ≤ 1 / ↑n

    With L = ⌈9 log n⌉ + 1 and T₁ = ⌈117 log n⌉ + 23, phase 1 fails with probability at most 1/n.

    theorem RumorPush.numeric_C {n : ℕ} (hn : 2 ≤ n) :
    (2 / 3) ^ ⌈6 * Real.log ↑n⌉₊ * ↑n ≤ 1 / ↑n

    With T₂ = ⌈6 log n⌉, phase 2 fails with probability at most 1/n.

    theorem RumorPush.push_informs_all_whp {n : ℕ} (hn : 2 ≤ n) (v₀ : Fin n) :
    prNotAllInformed n v₀ (⌈117 * Real.log ↑n⌉₊ + 23 + ⌈6 * Real.log ↑n⌉₊) ≤ 2 / ↑n

    Rumor spreading on the complete graph, push model, O(log n) rounds.

    Start the uniform push protocol on K_n (n ≥ 2) with the single informed node v₀. After T = (⌈117 log n⌉ + 23) + ⌈6 log n⌉ = O(log n) rounds, all n nodes are informed with probability at least 1 - 2/n.