Documentation

Epidemics.Revisited.Instances

Sharp upper bounds for push, pull and push–pull on K_n (EPI-8, instances) #

Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version arXiv:2303.11150), Theorems 51, 52 and 53 (upper bounds): the expected rumor spreading time on the complete graph is at most

Here the tails are exponential as well: overshooting these times by r rounds has probability at most A e^{-κ r}. The start may be any nonempty set of informed nodes (the paper starts from one node). The proofs instantiate the general theorems with the conditions verified in Protocols: push by spreading_upper_tail (Theorems 21 and 31), pull and push–pull by spreading_upper_tail_double (Theorems 21 and 43); the middle range of Lemma 19 is empty, since both thresholds are n/2.

The side condition of the push shrinking conditions: e^{-1} + (2/e)(1/2) = 2/e < 1.

theorem Epidemics.Revisited.half_pow_lt_one :
1 * (1 / 2) ^ (2 - 1) < 1

The side condition of the pull and push–pull double shrinking conditions: 1 · (1/2)^{2-1} < 1.

theorem Epidemics.Revisited.middle_empty {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) :
1 / 2 * ↑n ≤ ↑S.card → 1 / 2 * ↑n < ↑n - ↑S.card → ∀ x ∉ S, 1 ≤ P.informProb S x

With f = g = 1/2 the middle range of Lemma 19 is empty.

theorem Epidemics.Revisited.push_spreading_tail :
∃ (A : ℝ) (κ : ℝ), 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.Nonempty → ∀ (r : ℕ), (push n).notYet (↑n) (⌈Real.logb 2 ↑n⌉₊ + ⌈Real.log ↑n⌉₊ + r) S ≤ A * Real.exp (-κ * ↑r)

Theorem 51 (upper bound), tail form: push informs all nodes of K_n within ⌈log₂ n⌉ + ⌈ln n⌉ + r rounds, except with probability at most A e^{-κ r}.

theorem Epidemics.Revisited.push_spreading_expect :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.Nonempty → ∀ (R : ℕ), ∑ t ∈ Finset.range R, (push n).notYet (↑n) t S ≤ Real.logb 2 ↑n + Real.log ↑n + B

Theorem 51 (upper bound): the expected time of push to inform all nodes of K_n is at most log₂ n + ln n + B, stated for every partial sum of the tail series E[T] = ∑_t P[T > t].

theorem Epidemics.Revisited.pull_spreading_tail :
∃ (A : ℝ) (κ : ℝ), 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.Nonempty → ∀ (r : ℕ), (pull n).notYet (↑n) (⌈Real.logb 2 ↑n⌉₊ + ⌈Real.logb 2 (Real.log ↑n)⌉₊ + r) S ≤ A * Real.exp (-κ * ↑r)

Theorem 52 (upper bound), tail form: pull informs all nodes of K_n within ⌈log₂ n⌉ + ⌈log₂ ln n⌉ + r rounds, except with probability at most A e^{-κ r}.

theorem Epidemics.Revisited.pull_spreading_expect :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.Nonempty → ∀ (R : ℕ), ∑ t ∈ Finset.range R, (pull n).notYet (↑n) t S ≤ Real.logb 2 ↑n + Real.logb 2 (Real.log ↑n) + B

Theorem 52 (upper bound): the expected time of pull to inform all nodes of K_n is at most log₂ n + log₂ ln n + B.

theorem Epidemics.Revisited.pushPull_spreading_tail :
∃ (A : ℝ) (κ : ℝ), 0 < κ ∧ ∃ (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.Nonempty → ∀ (r : ℕ), (pushPull n).notYet (↑n) (⌈Real.logb 3 ↑n⌉₊ + ⌈Real.logb 2 (Real.log ↑n)⌉₊ + r) S ≤ A * Real.exp (-κ * ↑r)

Theorem 53 (upper bound), tail form: push–pull informs all nodes of K_n within ⌈log₃ n⌉ + ⌈log₂ ln n⌉ + r rounds, except with probability at most A e^{-κ r}.

theorem Epidemics.Revisited.pushPull_spreading_expect :
∃ (B : ℝ) (N : ℕ), ∀ (n : ℕ), N ≤ n → ∀ (S : Finset (Fin n)), S.Nonempty → ∀ (R : ℕ), ∑ t ∈ Finset.range R, (pushPull n).notYet (↑n) t S ≤ Real.logb 3 ↑n + Real.logb 2 (Real.log ↑n) + B

Theorem 53 (upper bound): the expected time of push–pull to inform all nodes of K_n is at most log₃ n + log₂ ln n + B.