Documentation

RumorSpread.PullPushPull

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

Starting the PUSH–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, Thm 2.1, in the weaker form O(log n) instead of log₃ n + O(log log n)]. Since PUSH–PULL dominates PUSH and PULL pathwise (run_subset_pushPullRun, pullRun_subset_pushPullRun), the bound follows from either push_informs_all_whp or pull_informs_all_whp; we use the latter, which needs no change in the number of rounds.

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

PUSH–PULL rumor spreading on the complete graph, O(log n) rounds [KSSV00, Thm 2.1, in O(log n) form].

Start the PUSH–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.