Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1, p. 1941 — for a ∉ C̄′, Σ_l X_l(t) → ∞ a.s. under every history-dependent policy

Proved
ConstrainedQueueing.Nonstationary.theorem_4_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

almost-sureconstrained-queueinginstabilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingstability-region

Consider a constrained queueing network with a single class of customers and one-slot service times: LLL queues, NNN servers, server iii moving one customer per activated slot from queue q(i)q(i)q(i) to queue h(i)h(i)h(i) or out of the system, and a constraint set SSS of activation sets that satisfies C.1 and contains the empty set. The arrivals Al(t)A_l(t)Al​(t) at queue lll in slot ttt are i.i.d. over ttt, independent across queues, with finite second moments; let al=E[Al(1)]a_l=E[A_l(1)]al​=E[Al​(1)] be the arrival rates.

Theorem 4.1. If a∉Cˉ′a\notin\bar C'a∈/Cˉ′, then for every policy π∈G~\pi\in\tilde Gπ∈G~ (every rule choosing, in each slot, an activation set as a function of the whole history of queue lengths, and never activating more servers of a queue than it has customers) and every initial state, the total number of customers in the system grows to infinity:

lim⁡t→∞∑l=1LXl(t)=∞a.s.(4.1)\lim_{t\to\infty}\sum_{l=1}^L X_l(t)=\infty\quad\text{a.s.} \tag{4.1}t→∞lim​l=1∑L​Xl​(t)=∞a.s.(4.1)

Together with the fact that a stationary policy stabilizes the system for every a∈C′a\in C'a∈C′ (Theorem 3.2 of the paper), this shows that nonstationary, history-dependent policies gain nothing in stability: the region Cˉ′\bar C'Cˉ′, determined by flows bounded by the convex hull of the activation vectors, is the limit of what any scheduler can sustain.

Formalization Note. The page states the theorem for a∈Cˉca\in\bar C^ca∈Cˉc, the complement of the closure of the stability region CCC of Definition 3.4; the introduction of §IV states it for (Cˉ′)c(\bar C')^c(Cˉ′)c, and Cˉ=Cˉ′\bar C=\bar C'Cˉ=Cˉ′ by Theorem 3.2. The formalization uses Cˉ′\bar C'Cˉ′, defined from flows (Cprime). Queues and servers are indexed from 0. A t is the arrival vector of slot t+1t+1t+1; the standing assumptions of §II become: iIndepFun of the vectors over time, IdentDistrib with A 0, iIndepFun of the components within each slot, and integrability of Al2A_l^2Al2​. The rate aaa is the mean of A 0. A policy maps the history X(0),…,X(t)X(0),\dots,X(t)X(0),…,X(t) to the activation set of slot t+1t+1t+1 and is admissible (IsAdmissiblePolicy: sets in SSS, no server activated for a nonexisting customer, the defining property of activation rules on p. 1938). X t ω is the run of (2.1) with M≡IM\equiv IM≡I for the arrivals of outcome ω\omegaω. The hypothesis ∅∈S\emptyset\in S∅∈S is the paper's standing convention.

Preamble
import Mathlib
import Definitions.Def_ConstrainedQueueing_Nonstationary_Model
Formal statement
namespace ConstrainedQueueing.Nonstationary

open MeasureTheory ProbabilityTheory Filter

/-- Theorem 4.1 (p. 1941): single class, one-slot service times. Let the arrival vectors `A t`
(arrivals at the `L` queues in slot `t + 1`) be i.i.d. in time, with independent components and
finite second moments, and let `a` be their mean. If `a` lies outside the closure of `C'`, then
for every admissible history-dependent policy `π` and every initial state, the total number of
customers in the system tends to infinity almost surely. -/
theorem theorem_4_1 {L N : ℕ} (net : Network L N) (hC1 : C1 net)
    (hS0 : (∅ : Finset (Fin N)) ∈ net.S)
    {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
    (A : ℕ → Ω → Fin L → ℕ) (hAmeas : ∀ t, Measurable (A t))
    (hindep : iIndepFun (fun t => A t) μ) (hident : ∀ t, IdentDistrib (A t) (A 0) μ μ)
    (hindepQ : ∀ t, iIndepFun (fun l ω => A t ω l) μ)
    (hsq : ∀ l, Integrable (fun ω => ((A 0 ω l : ℝ)) ^ 2) μ)
    (a : Fin L → ℝ) (hmean : ∀ l, a l = ∫ ω, (A 0 ω l : ℝ) ∂μ)
    (ha : a ∉ closure (Cprime net))
    (π : HistPolicy L N) (hπ : IsAdmissiblePolicy net π) (x0 : Fin L → ℕ)
    (X : ℕ → Ω → Fin L → ℕ) (hX : ∀ ω, IsRun net π x0 (fun t => A t ω) (fun t => X t ω)) :
    ∀ᵐ ω ∂μ, Tendsto (fun t => ∑ l, (X t ω l : ℝ)) atTop atTop := by sorry

end ConstrainedQueueing.Nonstationary
Source
Tassiulas and Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Trans. Automat. Control 37(12) (1992), p. 1941, §IV, Theorem 4.1, (4.1); statistical assumptions p. 1938
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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