Lower bound for pull on K_n: the two phases (EPI-8, Theorem 52) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version
arXiv:2303.11150), Theorem 52 (lower bound): pull needs log₂ n + log₂ ln n - O(1) rounds.
- Growth (the role of Theorem 27 with
γ = 1): an uninformed node is informed with probability|S| / n, so the expected number of informed nodes at most doubles per round (pull_expect_card_le), and at leastmnodes are informed aftertrounds with probability at most2^t |S| / m(pull_growth_lower). - Final phase (the role of Theorem 48 with
ℓ = 2): withuuninformed nodes, each stays uninformed with probabilityu / n(pull_expect_uninformed), and fewer thanu² / (2n)stay uninformed with probability at most4 n² / u³(pull_round_lower). From at leastn / 2uninformed nodes, informing everybody withinlog₂ ln n - r₀rounds has probabilityO(n^{-1/2})(pull_final_lower).
One round of the final phase (Lemma 49 for pull, ℓ = 2, a = 1): with u = n - |S|
uninformed nodes, fewer than u² / (2n) nodes stay uninformed with probability at most
4 n² / u³.
Final phase (Theorem 48 for pull, ℓ = 2): from at least n / 2 uninformed nodes, pull
informs all nodes within log₂ ln n - r₀ rounds with probability at most C n^{-1/2}.