Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.1 — without immediate feedback, the work-conserving fluid model of a two-station Kelly-type line is stable

Proved
DaiWeissFluid.KellyType.theorem6_1

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

fluid-modelkelly-networkp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1queueing-network-stabilityreentrant-line

Consider a reentrant line with two stations and KKK classes, with positive mean service times mkm_kmk​, which is of Kelly type: every visit to station iii has the same mean service time βi\beta_iβi​, mk=βσ(k)m_k = \beta_{\sigma(k)}mk​=βσ(k)​. Assume the routing has no immediate feedback, σ(k+1)≠σ(k)\sigma(k+1) \ne \sigma(k)σ(k+1)=σ(k) for k=1,…,K−1k = 1, \dots, K-1k=1,…,K−1, and the traffic condition (1.7), ρi=∑k∈Cimk<1\rho_i = \sum_{k \in C_i} m_k < 1ρi​=∑k∈Ci​​mk​<1 for i=1,2i = 1,2i=1,2. Then the work-conserving fluid model (1.8)–(1.13) is stable: there is δ>0\delta > 0δ>0 such that every work-conserving fluid solution with ∣Q(0)∣=1|Q(0)| = 1∣Q(0)∣=1 satisfies

Qk(t)=0for all t≥δ and k=1,…,K.Q_k(t) = 0 \qquad \text{for all } t \ge \delta \text{ and } k = 1,\dots,K.Qk​(t)=0for all t≥δ and k=1,…,K.

The paper's Theorem 6.1 reads: "Consider a two station Kelly-type reentrant network. Assume that routing does not have immediate feedback. Then any work-conserving policy is stable." It asserts stability of every work-conserving policy; its proof establishes the fluid-model stability formalized here, and the queueing-level conclusion follows from Theorem 1.1 of the paper (Dai 1995, Thm 4.3), which is cited and not formalized. Since every work-conserving policy's fluid model is a subset of the work-conserving fluid model, the statement covers all such policies at once. Both hypotheses are needed: Remark 2 of the paper gives a Kelly-type two-station line with immediate feedback that is unstable under a static priority, and Remark 3 a three-station counterexample.

Formalization Note Indices are 0-based. The statement holds for every KKK, of either parity, and the route may begin at either station; the paper proves K=2nK = 2nK=2n and says K=2n+1K = 2n+1K=2n+1 "can be proved similarly". mk>0m_k > 0mk​>0 is an explicit hypothesis (the paper takes it for granted, as mkm_kmk​ are means of service times). Stability is Definition 1.3, which only constrains solutions with ∣Q(0)∣=∑kQk(0)=1|Q(0)| = \sum_k Q_k(0) = 1∣Q(0)∣=∑k​Qk​(0)=1.

Preamble
import Mathlib
import Definitions.Def_DaiWeissFluid_KellyType_FluidModel
import Definitions.Def_DaiWeissFluid_KellyType_KellyLine
Formal statement
namespace DaiWeissFluid.KellyType

/-- Theorem 6.1, p. 130: in a two-station Kelly-type reentrant line (station means `β`) whose
route has no immediate feedback, under the traffic condition (1.7), the work-conserving fluid
model (1.8)–(1.13) is stable in the sense of Definition 1.3. -/
theorem theorem6_1 {K : ℕ} (L : ReentrantLine 2 K) (hm : ∀ k, 0 < L.m k)
    (hρ : ∀ i, L.ρ i < 1) (β : Fin 2 → ℝ) (hkelly : L.IsKellyType β)
    (hfb : L.NoImmediateFeedback) :
    DaiWeissFluid.ThreeBuffer.FluidStable L.IsWorkConserving := by sorry

end DaiWeissFluid.KellyType
Source
Dai and Weiss, Stability and instability of fluid models for reentrant lines, Math. Oper. Res. 21(1) (1996), p. 130, Theorem 6.1
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