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.
Probability that not all nodes are informed after T rounds, starting
from the single informed node v₀.
Equations
- RumorPush.prNotAllInformed n v₀ T = Dynamics.expList (RumorPush.Tgt n) T fun (l : List (RumorPush.Tgt n)) => if RumorPush.run {v₀} l = Finset.univ then 0 else 1
Instances For
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).
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.