Double exponential shrinking regime (EPI-8, definitions) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version
arXiv:2303.11150), Appendix B.6: when every uninformed node stays uninformed with probability
proportional to a power ℓ - 1 > 0 of the fraction of uninformed nodes, this fraction is
roughly raised to the power ℓ in each round, and the last g n nodes are informed within
log_ℓ ln n + O(1) rounds. This regime occurs in protocols with pull operations.
UpperDoubleShrinkingis Definition 13 (the upper double exponential shrinking conditions), in the same form asRumorProcess.UpperShrinking: bounds for every state with betweenn^{1-α}andg nuninformed nodes, for one value ofn.FastFinishingis the second hypothesis of Theorem 43: belown^{1-α}uninformed nodes, every uninformed node stays uninformed with probability at mostn^{-τ}.
Definition 13 (upper double exponential shrinking conditions), for one value of n.
In every round started from S with u = n - |S| uninformed nodes, n^{1-α} ≤ u ≤ g n:
(i) every uninformed node stays uninformed with probability at most a (u / n)^{ℓ-1}, that is,
1 - p_{n-u} ≤ a (u/n)^{ℓ-1}, and
(ii) the covariance numbers satisfy c_{n-u} ≤ c n / u².
The paper requires these for all large n, with g, α ∈ [0, 1], ℓ > 1, a, c ≥ 0 and
a g^{ℓ-1} < 1; the theorems quantify over n accordingly.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The second hypothesis of Theorem 43, for one value of n: in every round started with at
most n^{1-α} uninformed nodes, every uninformed node stays uninformed with probability at
most n^{-τ}.