IsOnlineClairvoyantScheduleGen
A deterministic clairvoyant online schedule generator on lists of requests produces a cache configuration at time t that depends only on the list of requests with arrival time at most t; specifically, for any two lists of deadline requests reqs₁ and reqs₂, if their sublists of requests arriving at or before t are equal, then the generator produces the same cache configuration at time t.
Statement
def IsOnlineClairvoyantScheduleGen {α : Type*} (Alg : List (DeadlineRequest α) → (ℕ → Finset α)) : Prop
- Defined in
- arXiv:2610.18767 Sec. 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 1
- DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
- Used by 3
- not_deadline_paging_upper_bound_k_plus_oneThe statement
deadline_paging_upper_bound_k_plus_oneis false: The statement (for every k≥1, every finite α with card ≥ k+1, every C₀ of… - IsCompetitiveRatioA schedule generator Alg is ρ-competitive for cache capacity k and initial cache C₀ if it is online, produces a feasible schedule whenever…
- deadline_paging_lower_bound_k_plus_halfFor every cache capacity k ≥ 1, every finite page universe α with at least k + 2 pages, every initial cache C₀ of size k, every schedule…
- not_deadline_paging_upper_bound_k_plus_oneThe statement
Read back from the Lean
For a type α, a function Alg : List (DeadlineRequest α) → ℕ → Finset α satisfies IsOnlineClairvoyantScheduleGen Alg if and only if for all request lists reqs₁ and reqs₂ and for all time steps t : ℕ, whenever the sublist of requests in reqs₁ with arrival time arrival ≤ t is identical (in elements and order) to the sublist of requests in reqs₂ with arrival time arrival ≤ t, the set of pages scheduled at time t, Alg reqs₁ t, is equal to Alg reqs₂ t.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Causality condition defining a deterministic clairvoyant online schedule generator on lists of requests. -/ def IsOnlineClairvoyantScheduleGen {α : Type*} (Alg : List (DeadlineRequest α) → (ℕ → Finset α)) : Prop := ∀ reqs₁ reqs₂ : List (DeadlineRequest α), ∀ t : ℕ, reqs₁.filter (fun r => r.arrival ≤ t) = reqs₂.filter (fun r => r.arrival ≤ t) → Alg reqs₁ t = Alg reqs₂ t