Documentation

Epidemics.Revisited.Protocols

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.

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 #

theorem Epidemics.Revisited.push_informProb {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(push n).informProb S x = 1 - (1 - 1 / ↑n) ^ S.card

Push: an uninformed node is informed with probability p_k = 1 - (1 - 1/n)^k.

theorem Epidemics.Revisited.pull_informProb {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(pull n).informProb S x = ↑S.card / ↑n

Pull: an uninformed node is informed with probability p_k = k / n.

theorem Epidemics.Revisited.pushPull_informProb {n : ℕ} {S : Finset (Fin n)} {x : Fin n} (hx : x ∉ S) :
(pushPull n).informProb S x = 1 - (1 - 1 / ↑n) ^ S.card * (1 - ↑S.card / ↑n)

Push–pull: an uninformed node is informed with probability p_k = 1 - (1 - 1/n)^k (1 - k/n).

theorem Epidemics.Revisited.push_homogeneous {n : ℕ} :
(push n).Homogeneous fun (k : ℕ) => 1 - (1 - 1 / ↑n) ^ k
theorem Epidemics.Revisited.pull_homogeneous {n : ℕ} :
(pull n).Homogeneous fun (k : ℕ) => ↑k / ↑n
theorem Epidemics.Revisited.pushPull_homogeneous {n : ℕ} :
(pushPull n).Homogeneous fun (k : ℕ) => 1 - (1 - 1 / ↑n) ^ k * (1 - ↑k / ↑n)
theorem Epidemics.Revisited.push_cov_nonpos {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(push n).cov S x y ≤ 0

Push: two distinct uninformed nodes are informed nonpositively correlated.

theorem Epidemics.Revisited.pull_cov_eq_zero {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(pull n).cov S x y = 0

Pull: two distinct uninformed nodes are informed independently.

theorem Epidemics.Revisited.pushPull_cov_nonpos {n : ℕ} {S : Finset (Fin n)} {x y : Fin n} (hx : x ∉ S) (hy : y ∉ S) (hxy : x ≠ y) :
(pushPull n).cov S x y ≤ 0

Push–pull: two distinct uninformed nodes are informed nonpositively correlated.

The conditions of the general upper bounds, with explicit constants #

theorem Epidemics.Revisited.push_upperGrowth {n : ℕ} :
(push n).UpperGrowth 1 (1 / 2) 0 0 (1 / 2)

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

theorem Epidemics.Revisited.pull_upperGrowth {n : ℕ} :
(pull n).UpperGrowth 1 0 0 0 (1 / 2)

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

theorem Epidemics.Revisited.pushPull_upperGrowth {n : ℕ} :
(pushPull n).UpperGrowth 2 (3 / 4) 0 0 (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}.