PagingWithDelayExecution
A structure PagingWithDelayExecution parameterized by page type α with decidable equality and cache capacity k : ℕ, consisting of the number of payments P : ℕ, offline fetch count F_opt : ℕ, offline delay D_opt : ℝ with 0 ≤ D_opt, a list of payment windows of length P, and an accounting property that (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt).
Statement
structure PagingWithDelayExecution (α : Type*) [DecidableEq α] (k : ℕ)
- Defined in
- arXiv:2610.18767 Section 2 & Section 3
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- PaymentWindowA structure PaymentWindow parameterized by page type α and cache capacity k : ℕ, consisting of a requested page : α, offline fetch count…
- Used by 3
- paging_with_delay_alg_costThe total cost incurred by the 1-FIFO algorithm in a paging with delay execution exec, defined as 2 * (exec.P : ℝ).
- paging_with_delay_opt_costThe total offline cost in a paging with delay execution exec, defined as the sum of offline fetches and offline delay: (exec.F_opt : ℝ) +…
- one_fifo_strictly_competitive_paging_with_delayFor any type α with decidable equality, any natural number k, and any paging with delay execution exec of type PagingWithDelayExecution α…
Read back from the Lean
A structure PagingWithDelayExecution, parameterized by a type α with decidable equality and a natural number k, bundling:
1. P : ℕ
2. F_opt : ℕ
3. D_opt : ℝ
4. A proof h_delay_nonneg that 0 ≤ D_opt
5. A list windows of elements of type PaymentWindow α k
6. A proof h_windows_len that the length of windows is P
7. A proof h_accounting that (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt).
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
/-- Execution of 1-FIFO and offline algorithm for paging with delay. -/ structure PagingWithDelayExecution (α : Type*) [DecidableEq α] (k : ℕ) where P : ℕ F_opt : ℕ D_opt : ℝ h_delay_nonneg : 0 ≤ D_opt windows : List (PaymentWindow α k) h_windows_len : windows.length = P h_accounting : (P : ℝ) ≤ (k + 1 : ℝ) * ((F_opt : ℝ) + D_opt)