Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, p. 1409 — a part reaching b_j after T^(j) leaves b_j within Γ^(j) + τ_j

Proved
ReentrantScheduling.FBFS.buffer_delay_bound

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

delayfbfsp2o-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). Then there are finite times T(1),…,T(l)T^{(1)},\dots,T^{(l)}T(1),…,T(l) such that every part π\piπ that arrives at buffer bjb_jbj​ at a time αj(π)>T(j)\alpha_j(\pi)>T^{(j)}αj​(π)>T(j) is served there and completes its service at bjb_jbj​ by

αj(π)+Γ(j)+τj,\alpha_j(\pi)+\Gamma^{(j)}+\tau_j ,αj​(π)+Γ(j)+τj​,

with Γ(j)\Gamma^{(j)}Γ(j) the busy-period constant of the proof of Theorem 1. In words: the delay of a part at bjb_jbj​ is at most Γ(j)+τj\Gamma^{(j)}+\tau_jΓ(j)+τj​ if it arrived at bjb_jbj​ after T(j)T^{(j)}T(j).

Summing these delays along the route gives the bound Γˉ=∑j<i(Γ(j)+τj)\bar\Gamma=\sum_{j<i}(\Gamma^{(j)}+\tau_j)Γˉ=∑j<i​(Γ(j)+τj​) on the time a part needs to reach bib_ibi​, which feeds the induction step.

Formalization Note Buffers are 0-based. The delay at bjb_jbj​ is measured from arrival at bjb_jbj​ to the end of service there. Arrival and start times live in WithTop ℝ; the conclusion forces the service start to be finite.

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

theorem buffer_delay_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 : Fin L.l → ℝ, ∀ (j : Fin L.l) (p : R.Part), R.entry p ≤ j →
      ((T j : ℝ) : WithTop ℝ) < R.arrive p j →
      R.start p j + ((L.τ j : ℝ) : WithTop ℝ) ≤
        R.arrive p j + ((L.Gamma lam γ j + L.τ j : ℝ) : WithTop ℝ) := 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, last paragraph of the right column
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