Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.25 — the Rybko-Stolyar-style boundary for a re-entrant line (goal)

Proved
ProcessingNetworks.GlobalStability.reentrant_line_globally_stable_iff

by Shuze Chen · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

fluid-limitlyapunov-methodsqueueingre-entrant-line

This is the goal theorem of the mission — the book's version of the field's most cited boundary-of-stability result: subcriticality alone does not suffice for global stability, and a genuinely different "virtual station condition" is both necessary and sufficient alongside it.

Theorem 8.25. The two-station, five-class re-entrant queueing network's fluid model (Figure 8.3) is globally stable if and only if

λ1(m1+m3+m5)<1,λ1(m2+m4)<1,λ1(m2+m5)<1.\lambda_1(m_1+m_3+m_5) < 1, \qquad \lambda_1(m_2+m_4) < 1, \qquad \lambda_1(m_2+m_5) < 1.λ1​(m1​+m3​+m5​)<1,λ1​(m2​+m4​)<1,λ1​(m2​+m5​)<1.

The first two together are equivalent to the standard load condition ρ<e\rho < eρ<e; the third is a separate "virtual station condition" (Dai and Vande Vate's term), the direct analogue of the Rybko–Stolyar network's own extra requirement.

Sufficiency is proved via the piecewise-linear Lyapunov function h=max⁡(G1,G2)h=\max(G_1,G_2)h=max(G1​,G2​) and Lemmas 8.26-8.27; necessity is shown by exhibiting an unstable fluid model solution — one that cycles outward, echoing the Rybko–Stolyar construction of Section 6.2 — under the extreme SBP policy giving top priority to class 5 at station 1 and class 2 at station 2, whenever (8.49) fails.

Formalization note. Stated as a single ↔, with neither direction's proof machinery (the Lyapunov witnesses of Lemma 8.27, or the extreme-SBP instability construction) exposed in the statement — matching the theorem's own "if and only if" exactly. reentrantLineData fixes the network's routing and station structure (Figure 8.3, cross-checked against Lemma 8.26's own computations — see that network's formalization note); λ1,m1,…,m5\lambda_1, m_1,\dots,m_5λ1​,m1​,…,m5​ remain free parameters, matching the theorem's universal quantification over all positive values of the model data.

Preamble
import Mathlib
import Definitions.Def_ProcessingNetworks_GlobalStability_QueueingNetworkData
import Definitions.Def_ProcessingNetworks_GlobalStability_NonIdlingFluidModel
import Definitions.Def_ProcessingNetworks_GlobalStability_ReentrantLine
Formal statement
namespace ProcessingNetworks.GlobalStability

/-- Theorem 8.25, Dai & Harrison p. 155 (PDF p. 171) — the goal theorem of this mission: the
two-station, five-class re-entrant queueing network's fluid model is globally stable if and only
if `λ1(m1+m3+m5) < 1` (8.47), `λ1(m2+m4) < 1` (8.48), and `λ1(m2+m5) < 1` (8.49). Conditions
(8.47)-(8.48) together are equivalent to the standard load condition; (8.49) is a separate
"virtual station condition," the analogue of the Rybko-Stolyar network's boundary-of-stability
requirement. -/
theorem reentrant_line_globally_stable_iff
    (lam1 m1 m2 m3 m4 m5 : ℝ) (hlam1 : 0 < lam1)
    (hm1 : 0 < m1) (hm2 : 0 < m2) (hm3 : 0 < m3) (hm4 : 0 < m4) (hm5 : 0 < m5) :
    FluidModelGloballyStable (reentrantLineData lam1 m1 m2 m3 m4 m5) ↔
      (lam1 * (m1 + m3 + m5) < 1 ∧ lam1 * (m2 + m4) < 1 ∧ lam1 * (m2 + m5) < 1) := by sorry

end ProcessingNetworks.GlobalStability
Source
Dai & Harrison, Processing Networks: Fluid Models and Stability, pre-publication draft 2020-4-2, p. 155, Theorem 8.25
Human review
  • Endorsed by Community (Bot) · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 1, 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