Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Condition (5.7) — slower-than-exponential backoff has critical rate zero

Proved
KellyStochasticNetworks.ack_scheme_critical_rate_zero

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

analysisprobabilitystochastic-networksstochastic-systems

Consider an acknowledgement-based random access scheme with non-negative retransmission function hhh, and let

Pt=(1+ν∑r=1th(r))exp⁡(−ν∑r=1th(r))P_t=\Bigl(1+\nu\sum_{r=1}^{t}h(r)\Bigr)\exp\Bigl(-\nu\sum_{r=1}^{t}h(r)\Bigr)Pt​=(1+νr=1∑t​h(r))exp(−νr=1∑t​h(r))

be the probability that fewer than two attempts are made in slot ttt of the externally jammed channel. Suppose the scheme backs off more slowly than exponentially, in the sense of the book's condition (5.7):

1log⁡t∑x=1th(x)⟶∞(t→∞).\frac{1}{\log t}\sum_{x=1}^{t}h(x)\longrightarrow\infty \qquad (t\to\infty).logt1​x=1∑t​h(x)⟶∞(t→∞).

Then for every arrival rate ν>0\nu>0ν>0 the series ∑t≥1Pt\sum_{t\ge1}P_t∑t≥1​Pt​ converges.

Since H(ν)=∑tPtH(\nu)=\sum_t P_tH(ν)=∑t​Pt​ is finite for every positive ν\nuν, the critical rate νc=inf⁡{ν:H(ν)<∞}\nu_c=\inf\{\nu : H(\nu)<\infty\}νc​=inf{ν:H(ν)<∞} is zero. By Theorem 5.11 that means the expected number of successful transmissions is finite at every positive arrival rate: the channel jams. In the book's words, this holds "for any acknowledgement-based scheme with slower than exponential backoff".

The threshold is sharp in the sense that matters for protocol design. A fixed retransmission probability, as in ALOHA, gives ∑x≤th(x)\sum_{x\le t}h(x)∑x≤t​h(x) growing linearly and so falls under this result; Ethernet's binary exponential backoff gives growth like log⁡2t\log_2 tlog2​t, exactly at the boundary, and has the positive critical rate νc=log⁡2\nu_c=\log 2νc​=log2. Exponential backoff is not a tuning choice but the minimum that makes a contention protocol work at all.

Formalization Note The conclusion is stated as summability of the sequence of slot probabilities at each fixed ν>0\nu>0ν>0, which is what "H(ν)<∞H(\nu)<\inftyH(ν)<∞" means and what the definition of νc\nu_cνc​ consumes; it is not stated as a claim about the infimum, which adds nothing once the set of such ν\nuν is known to be all of (0,∞)(0,\infty)(0,∞). The hypothesis is condition (5.7) verbatim, as a limit; the quotient is not meaningful at t=0,1t=0,1t=0,1, where log⁡t≤0\log t\le0logt≤0, and divergence being eventual makes that immaterial. Beyond non-negativity no regularity of hhh is assumed.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_RandomAccess
Formal statement
namespace KellyStochasticNetworks

theorem ack_scheme_critical_rate_zero (h : ℕ → ℝ) (hh : ∀ x, 0 ≤ h x)
    (hgrow : Filter.Tendsto (fun t : ℕ => ackAttemptRate h t / Real.log t)
        Filter.atTop Filter.atTop)
    (ν : ℝ) (hν : 0 < ν) :
    Summable (fun t : ℕ => ackSlotProb h ν (t + 1)) := by sorry

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, p. 123 (PDF p. 131), condition (5.7): 'More generally, nu_c = 0 whenever (log t)^{-1} sum_{x=1}^{t} h(x) -> infinity as t -> infinity, (5.7) since this implies sum_{t=1}^{infinity} P_t < infinity for any nu > 0 (Exercise 5.8). In this sense, the expected number of successful transmissions is finite for any acknowledgement-based scheme with slower than exponential backoff.' With P_t from p. 120. sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me