DeadlineRequest
structure
A request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤ deadline.
Statement
structure DeadlineRequest (α : Type*)
- Defined in
- arXiv:2610.18767 Sec. 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 11
- 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.
- instanceHorizonThe finite time horizon of a list of deadline requests, defined as one more than the maximum deadline, or zero if empty.
- 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…
- IsFeasibleScheduleA schedule of cache configurations of size at most k is feasible for a list of deadline requests starting from initial cache C₀ if it…
- 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…
- IsOnlineClairvoyantScheduleGenA deterministic clairvoyant online schedule generator on lists of requests produces a cache configuration at time t that depends only on…
- not_deadline_paging_upper_bound_k_plus_oneThe statement
Read back from the Lean
Given a type α, the structure DeadlineRequest α consists of:
1. a value page of type α,
2. a natural number arrival,
3. a natural number deadline, and
4. a proof h_deadline that arrival ≤ deadline.
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
/-- A request in online paging with deadlines. -/ structure DeadlineRequest (α : Type*) where page : α arrival : ℕ deadline : ℕ h_deadline : arrival ≤ deadline