Example 5.8 — ALOHA satisfies condition (5.7)
ProvedKellyStochasticNetworks.aloha_attempt_rateThe ALOHA protocol is the acknowledgement-based scheme with and for every , where is the retransmission probability. Two facts.
- Its attempt-rate partial sums are exactly linear:
- Consequently it satisfies condition (5.7):
Linear growth is much faster than logarithmic, so ALOHA is at the far end of the range the condition covers. Combined with the goal of this mission, it gives for ALOHA, which is the analytic counterpart of Proposition 5.3: whatever the arrival rate, the channel eventually jams. The contrast to hold in mind is Ethernet's binary exponential backoff, where grows at exactly the critical rate and produces .
Formalization Note The first identity is stated at so that the sum is over a non-empty range of slots and no index has to be decremented. The quotient in the second is not meaningful at , where ; divergence is an eventual statement, so this is immaterial.
import Mathlib import Definitions.Def_KellyStochasticNetworks_RandomAccess
namespace KellyStochasticNetworks
theorem aloha_attempt_rate (f : ℝ) (hf : 0 < f) :
(∀ t : ℕ, ackAttemptRate (alohaH f) (t + 1) = 1 + (t : ℝ) * f)
∧ Filter.Tendsto (fun t : ℕ => ackAttemptRate (alohaH f) t / Real.log t)
Filter.atTop Filter.atTop := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.