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