The push, pull and push–pull protocols on the complete graph (EPI-8, instances) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version arXiv:2303.11150), Appendix C of the long version (Theorems 51, 52 and 53).
In one round every node calls a node chosen uniformly at random among all n nodes,
independently; following the paper's convention for complete graphs, a node may call itself.
The calls of a round are a uniform function c : Fin n → Fin n (calls n); the
definitions are in ProtocolsDefs.
- push: every informed node sends the rumor to the node it calls;
- pull: every uninformed node that calls an informed node becomes informed;
- push–pull: both, so a node becomes informed if it calls an informed node or is called by one.
The per-state quantities of the general theory are computed exactly: with k = |S| informed
nodes, an uninformed node becomes informed with probability 1 - (1 - 1/n)^k (push), k / n
(pull) and 1 - (1 - 1/n)^k (1 - k/n) (push–pull); the three protocols are homogeneous; the
events that two distinct uninformed nodes become informed are nonpositively correlated (and
independent for pull). From these, the conditions of the general upper bounds hold with
explicit constants.
Exact one-round probabilities #
The conditions of the general upper bounds, with explicit constants #
Push satisfies the upper exponential growth conditions in [1, n/2[ with γ = 1,
a = 1/2, b = c = 0: p_k ≥ (k/n)(1 - k/(2n)).
Push satisfies the upper exponential shrinking conditions from n/2 uninformed nodes on,
with ρ = 1, a = 2/e, c = 0: 1 - p_{n-u} = (1 - 1/n)^{n-u} ≤ e^{-1} + (2/e)(u/n).
Pull satisfies the upper exponential growth conditions in [1, n/2[ with γ = 1,
a = b = c = 0: p_k = k/n.
Pull satisfies the upper double exponential shrinking conditions with ℓ = 2, a = 1,
c = 0, g = 1/2, α = 1/2: 1 - p_{n-u} = u/n.
Pull finishes fast below √n uninformed nodes: 1 - p_{n-u} = u/n ≤ n^{-1/2}.
Push–pull satisfies the upper exponential growth conditions in [1, n/2[ with γ = 2,
a = 3/4, b = c = 0: p_k ≥ 2(k/n)(1 - 3k/(4n)).
Push–pull satisfies the upper double exponential shrinking conditions with ℓ = 2,
a = 1, c = 0, g = 1/2, α = 1/2: 1 - p_{n-u} = (u/n)(1 - 1/n)^{n-u} ≤ u/n.
Push–pull finishes fast below √n uninformed nodes: 1 - p_{n-u} ≤ u/n ≤ n^{-1/2}.