Condition (5.7) — slower-than-exponential backoff has critical rate zero
ProvedKellyStochasticNetworks.ack_scheme_critical_rate_zeroConsider an acknowledgement-based random access scheme with non-negative retransmission function , and let
be the probability that fewer than two attempts are made in slot of the externally jammed channel. Suppose the scheme backs off more slowly than exponentially, in the sense of the book's condition (5.7):
Then for every arrival rate the series converges.
Since is finite for every positive , the critical rate 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 growing linearly and so falls under this result; Ethernet's binary exponential backoff gives growth like , exactly at the boundary, and has the positive critical rate . 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 , which is what "" means and what the definition of consumes; it is not stated as a claim about the infimum, which adds nothing once the set of such is known to be all of . The hypothesis is condition (5.7) verbatim, as a limit; the quotient is not meaningful at , where , and divergence being eventual makes that immaterial. Beyond non-negativity no regularity of is assumed.
import Mathlib import Definitions.Def_KellyStochasticNetworks_RandomAccess
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 KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.