Lemma 1 1): a queued buffer completes its next run within
ProvedKumarSeidman.Supervisor.lemma1_wait_boundConsider a system satisfying the capacity condition (1), supervisor parameters satisfying (24) and thresholds , and a supervised trajectory. Let be a buffer of machine that enters the priority queue at time . Then its subsequent processing run exists, and the time at which it is completed satisfies
This is the basic waiting-time guarantee of the supervisor: once a buffer is queued, the machine must reach it within a bounded time, whatever the underlying policy does.
Formalization Note As on the page, is an instant at which enters (Lean EntersQ: it is in at , and or it was not waiting in just before). is not a separate state: a buffer is in exactly when the machine's current run is not on it and its level exceeds . Existence of the subsequent run is part of the conclusion.
import Mathlib import Definitions.Def_KumarSeidman_Supervisor_System import Definitions.Def_KumarSeidman_Supervisor_Trajectory import Definitions.Def_KumarSeidman_Supervisor_Mechanism
namespace KumarSeidman.Supervisor
/-- Lemma 1 1) (Kumar–Seidman 1990, p. 296, (25)–(26)). If buffer `b` enters the priority
queue `Q_m` (`m = μ_b`) at time `t_in`, then its subsequent processing run exists and is
completed by `t_in + γ_m − ζ_m`. -/
theorem lemma1_wait_bound {P M : ℕ} (S : System P M) (hcap : S.CapacityCondition)
(γ : Fin M → ℝ) (hγ : GammaCondition S γ) (z : Buffer S → ℝ) (hz : ∀ b, 0 ≤ z b)
(T : Trajectory S) (hT : T.Supervised γ z) (b : Buffer S) (tIn : ℝ)
(hin : T.EntersQ z b tIn) :
∃ k : ℕ, T.IsNextRun b tIn k ∧ T.HasNext (S.mach b) k ∧
T.s (S.mach b) (k + 1) - tIn ≤ γ (S.mach b) - zeta S γ (S.mach b) := by sorry
end KumarSeidman.Supervisor
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.