IsFeasibleSchedule
A schedule of cache configurations of size at most k is feasible for a list of deadline requests starting from initial cache C₀ if it starts at C₀, keeps cache size at most k at all times, and caches each requested page at some time between its arrival and deadline.
Statement
def IsFeasibleSchedule {α : Type*} (k : ℕ) (C₀ : Finset α) (sched : ℕ → Finset α) (reqs : List (DeadlineRequest α)) : 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 8
- 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… - deadline_paging_min_cost_schedule_existsEvery feasible deadline-paging instance admits a feasible schedule whose fetch cost over the instance horizon is minimal among all…
- deadline_paging_cost_zero_iff_pages_subset_cacheA feasible instance can be served at fetch cost zero iff every requested page is already in the initial cache.
- deadline_paging_feasible_sublistFeasibility of a schedule for a request list passes to any sublist of the requests.
- deadline_paging_opt_cost_ge_pages_outside_cacheEvery feasible schedule must fetch each requested page outside the initial cache at least once, so its fetch cost is at least the number…
- 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…
- deadline_paging_feasible_iff_exists_service_timeAn instance is feasible iff one can assign every request a service time inside its window so that each non-zero time slot sees at most k…
- not_deadline_paging_upper_bound_k_plus_oneThe statement
Read back from the Lean
Given a type α, a natural number k, an initial finite set C₀ : Finset α, a schedule sched : ℕ → Finset α, and a list reqs of deadline requests (each having a page r.page : α, arrival time r.arrival : ℕ, deadline r.deadline : ℕ, and a proof that r.arrival ≤ r.deadline), IsFeasibleSchedule k C₀ sched reqs asserts that:
1. sched 0 = C₀ (the schedule starts at configuration C₀ at time 0),
2. For all t : ℕ, the cardinality of sched t is at most k, and
3. For every request r in reqs, there exists a time t : ℕ such that r.arrival ≤ t, t ≤ r.deadline, and r.page ∈ sched 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
/-- Feasibility of a cache schedule for an instance of paging with deadlines. -/ def IsFeasibleSchedule {α : Type*} (k : ℕ) (C₀ : Finset α) (sched : ℕ → Finset α) (reqs : List (DeadlineRequest α)) : Prop := sched 0 = C₀ ∧ (∀ t, (sched t).card ≤ k) ∧ (∀ r ∈ reqs, ∃ t, r.arrival ≤ t ∧ t ≤ r.deadline ∧ r.page ∈ sched t)