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