paging_with_delay_alg_cost
def
The total cost incurred by the 1-FIFO algorithm in a paging with delay execution exec, defined as 2 * (exec.P : ℝ).
Statement
def paging_with_delay_alg_cost {α : Type*} [DecidableEq α] {k : ℕ} (exec : PagingWithDelayExecution α k) : ℝ
- Defined in
- arXiv:2610.18767 Observation 3.1
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- PagingWithDelayExecutionA structure PagingWithDelayExecution parameterized by page type α with decidable equality and cache capacity k : ℕ, consisting of the…
- Used by 1
- 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 definition of paging_with_delay_alg_cost: for a type α with decidable equality, a natural number k, and an execution exec : PagingWithDelayExecution α k, the algorithm cost is defined to be the real number 2 * (exec.P : ℝ), where exec.P is the natural number field P of exec.
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
/-- Total cost of 1-FIFO: 2 per payment. -/ def paging_with_delay_alg_cost {α : Type*} [DecidableEq α] {k : ℕ} (exec : PagingWithDelayExecution α k) : ℝ := 2 * (exec.P : ℝ)