Double exponential shrinking regime, upper bound, and the total spreading time (EPI-8) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version
arXiv:2303.11150), Theorem 43 (upper bounds; Theorem 3 of the overview, whose conditions,
Definition 5, imply Definition 13 together with fast finishing): under the upper double
exponential shrinking conditions (Definition 13) and fast finishing below n^{1-α} uninformed
nodes, once at most g n nodes are uninformed, all nodes are informed within
log_ℓ ln n + O(1) rounds in expectation, and overshooting this by r rounds has probability
O(n^{A' - α' r}).
The total spreading time: Theorem 21 (growth from one node to f n nodes), Lemma 19 (from
f n informed nodes to at most g n uninformed ones) and Theorem 43 combine to
E[T(1, n)] ≤ log_{1+γ} n + log_ℓ ln n + O(1) with an exponential tail, the way the paper
obtains the spreading times of the pull and push–pull protocols (Theorems 52 and 53).
As in Growth and Shrinking, the process may start from any admissible set of informed nodes,
and expected times are bounded through all finite partial sums of the tail series
∑_t P[T > t].
Theorem 43, tail bound: under the upper double exponential shrinking conditions and fast
finishing, starting with at most g n uninformed nodes, some node is still uninformed after
⌈log_ℓ ln n⌉ + r rounds with probability at most C n^{A' - α' r}. The constants and the
threshold N depend only on ℓ, a, c, g, α, τ.
Theorem 43, expectation: under the same conditions, E[T(⌈(1 - g) n⌉, n)] ≤ log_ℓ ln n + B,
stated for every partial sum of the tail series E[T] = ∑_t P[T > t].
Total spreading time with a double exponential shrinking regime, tail bound (Theorems 21
and 43 composed through Lemma 19): under the upper exponential growth conditions in [1, f n[
(with γ between two positive constants), the upper double exponential shrinking conditions
and fast finishing, and, in between, a probability at least p > 0 for every uninformed node
to become informed, some node is still uninformed after
⌈log_{1+γ} n⌉ + ⌈log_ℓ ln n⌉ + r rounds with probability at most A e^{-κ r}. The constants
depend only on the parameters of the conditions.
Total spreading time with a double exponential shrinking regime, expectation: under the
same conditions, E[T(1, n)] ≤ log_{1+γ} n + log_ℓ ln n + B, stated for every partial sum of
the tail series E[T] = ∑_t P[T > t].