Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, p. 1409 — a 1-busy period commencing at T₁ > 0 lasts at most Γ^(1)

Proved
ReentrantScheduling.FBFS.gamma1_busy_period_bound

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

busy-periodfbfsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing-networkreentrant-line

Consider a nonacyclic flow line operated under first buffer first serve (FBFS), with releases satisfying the burstiness constraint (1) with constants λ,γ≥0\lambda,\gamma\ge0λ,γ≥0 and load ρ=λwˉ<1\rho=\lambda\bar w<1ρ=λwˉ<1 (3). Let 0<T1≤T20<T_1\le T_20<T1​≤T2​, and suppose that:

  1. a 1-busy period commences at T1T_1T1​: for some δ>0\delta>0δ>0, no part waits in buffer b1b_1b1​ at any time in (T1−δ,T1)(T_1-\delta,T_1)(T1​−δ,T1​);
  2. [T1,T2][T_1,T_2][T1​,T2​] is a 1-busy period: at every t∈[T1,T2]t\in[T_1,T_2]t∈[T1​,T2​] some part waits in b1b_1b1​.

Then

T2−T1≤Γ(1)=(2τˉ+γτ1mσ1)(1−λτ1mσ1)−1,τˉ=max⁡jτj.T_2-T_1\le\Gamma^{(1)}=\Big(2\bar\tau+\frac{\gamma\tau_1}{m_{\sigma_1}}\Big)\Big(1-\frac{\lambda\tau_1}{m_{\sigma_1}}\Big)^{-1},\qquad \bar\tau=\max_j\tau_j .T2​−T1​≤Γ(1)=(2τˉ+mσ1​​γτ1​​)(1−mσ1​​λτ1​​)−1,τˉ=jmax​τj​.

This is the base case of the induction that proves Theorem 1: once buffer b1b_1b1​ has emptied, it never stays continuously occupied for longer than Γ(1)\Gamma^{(1)}Γ(1).

Formalization Note Buffer b1b_1b1​ is Lean index 0. The page assumes T1>T(1)T_1>T^{(1)}T1​>T(1), the first time b1b_1b1​ empties, only to make "commences" meaningful; the statement assumes the commencing condition itself and T1>0T_1>0T1​>0, a mild generalization. Waiting excludes parts in service, as xi(t)x_i(t)xi​(t) does on p. 1409.

Preamble
import Mathlib
import Definitions.Def_ReentrantScheduling_FBFS_Model
import Definitions.Def_ReentrantScheduling_FBFS_Constants
Formal statement
namespace ReentrantScheduling.FBFS

theorem gamma1_busy_period_bound
    (L : Line) (lam γ : ℝ) (hlam : 0 ≤ lam) (hγ : 0 ≤ γ) (hload : L.load lam < 1)
    (R : Run L) (hR : R.Admissible L.fbfs) (harr : R.Arrivals lam γ)
    (T₁ T₂ : ℝ) (hT₁ : 0 < T₁) (hT₁₂ : T₁ ≤ T₂)
    (hcommence : ∃ δ > 0, ∀ t : ℝ, T₁ - δ < t → t < T₁ →
      ∀ q, ¬ R.Waiting q ⟨0, L.l_pos⟩ t)
    (hbusy : ∀ t : ℝ, T₁ ≤ t → t ≤ T₂ → R.Busy ⟨0, L.l_pos⟩ t) :
    T₂ - T₁ ≤ L.Gamma lam γ ⟨0, L.l_pos⟩ := by sorry

end ReentrantScheduling.FBFS
Source
Lu & Kumar, Distributed Scheduling Based on Due Dates and Buffer Priorities, IEEE TAC 36(12), 1991, p. 1409, proof of Theorem 1, the case i = 1 (bound on Γ^(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