Exercise 5.8 — a scheme that gives up has
ProvedKellyStochasticNetworks.ack_scheme_summable_hConsider an acknowledgement-based scheme whose retransmission function is non-negative and summable, . By the first Borel–Cantelli lemma a packet then makes only finitely many attempts — the scheme discards it after finitely many tries. Show that its critical rate is infinite: for every arrival rate ,
The reason is immediate once stated: if converges to a finite limit , then converges to , and a series whose terms do not tend to zero diverges.
This is the opposite extreme from the goal of this mission. A scheme that retransmits persistently enough to satisfy condition (5.7) jams at every positive rate; a scheme that gives up entirely has infinite at every positive rate, so infinitely many slots stay uncontested — at the cost of the packets it discarded. Between them lie the schemes with a finite positive , of which Ethernet is one.
Formalization Note "" is stated as failure of summability of the sequence of slot probabilities, which is the form the argument produces and the form the definition of uses.
import Mathlib import Definitions.Def_KellyStochasticNetworks_RandomAccess
namespace KellyStochasticNetworks
theorem ack_scheme_summable_h (h : ℕ → ℝ) (hh : ∀ x, 0 ≤ h x) (hsum : Summable h)
(ν : ℝ) (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.