scheduleCost
def
The total fetch cost of a cache schedule up to time T, defined as the sum over time steps of the number of newly fetched pages.
Statement
def scheduleCost {α : Type*} [DecidableEq α] (sched : ℕ → Finset α) (T : ℕ) : ℕ
- Defined in
- arXiv:2610.18767 Sec. 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 6
- 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_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…
- not_deadline_paging_upper_bound_k_plus_oneThe statement
Read back from the Lean
Given a type α with decidable equality, a schedule sched : ℕ → Finset α, and a time bound T : ℕ, scheduleCost sched T is defined as the sum over t ∈ Finset.range T (i.e., t from 0 to T - 1) of the cardinality of the set difference (sched (t + 1)) \ (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
/-- The total fetch cost of a cache schedule up to time T. -/ def scheduleCost {α : Type*} [DecidableEq α] (sched : ℕ → Finset α) (T : ℕ) : ℕ := ∑ t ∈ Finset.range T, ((sched (t + 1)) \ (sched t)).card