Documentation

RumorSpread.PullMain

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

Starting the PULL protocol on K_n (n ≥ 2) from a single informed node, after ⌈160 log n⌉ rounds all n nodes are informed with probability at least 1 - 2/n [KSSV00, §2]. The constant is deliberately crude, as for PUSH in Main.lean: the growth phase (informed set up to n/2) and the shrinking phase (expected uninformed count contracting, see pull_avg_uninformed) are glued exactly as in prNotAllInformed_le: the proof instantiates the generic notAllOf_le_two_div (PullPhases.lean) with the PULL inputs of PullGood.lean.

theorem RumorPush.pull_informs_all_whp {n : ℕ} (hn : 2 ≤ n) (v₀ : Fin n) :

PULL rumor spreading on the complete graph, O(log n) rounds [KSSV00, §2].

Start the PULL protocol on K_n (n ≥ 2) with the single informed node v₀. After ⌈160 log n⌉ rounds the probability that some node is still uninformed is at most 2/n.