Documentation

Epidemics.Revisited.DoubleShrinkingDefs

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.

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^{-τ}.

    Equations
    Instances For