Proof of Theorem 1, pp. 1409–1410 — after finite times T^(i), every i-busy period lasts at most Γ^(i)
ProvedReentrantScheduling.FBFS.busy_period_boundConsider a nonacyclic flow line operated under first buffer first serve (FBFS), with releases satisfying the burstiness constraint (1) with constants and load (3). Then there are finite times such that for every buffer index and every -busy period with ,
where is defined recursively by and
An -busy period is an interval at every instant of which some part waits in a buffer , , at the center .
This is the induction hypothesis of the proof of Theorem 1, established for every ; the constants depend only on the line and on , while the times depend on the run, in particular on the initial state.
Formalization Note Buffers are 0-based (i is the paper's ). The page prints as a product of the two brackets; the Lean uses the quotient that the preceding inequality yields (see the Constants definition). The times are existentially quantified after the run.
import Mathlib import Definitions.Def_ReentrantScheduling_FBFS_Model import Definitions.Def_ReentrantScheduling_FBFS_Constants
namespace ReentrantScheduling.FBFS
theorem 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 : Fin L.l → ℝ, ∀ (i : Fin L.l) (T₁ T₂ : ℝ), T i < T₁ → T₁ ≤ T₂ →
(∀ t : ℝ, T₁ ≤ t → t ≤ T₂ → R.Busy i t) →
T₂ - T₁ ≤ L.Gamma lam γ i := by sorry
end ReentrantScheduling.FBFS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.