one_fifo_strictly_competitive_paging_with_delay
For any type α with decidable equality, any natural number k, and any paging with delay execution exec of type PagingWithDelayExecution α k, the 1-FIFO algorithm cost paging_with_delay_alg_cost exec is at most (2 * (k : ℝ) + 2) times the optimal offline cost paging_with_delay_opt_cost exec.
Statement
theorem one_fifo_strictly_competitive_paging_with_delay {α : Type*} [DecidableEq α] {k : ℕ} (exec : PagingWithDelayExecution α k) : paging_with_delay_alg_cost exec ≤ (2 * (k : ℝ) + 2) * paging_with_delay_opt_cost exec
- Formalizes
- arXiv:2610.18767 Theorem 1.2
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- PagingWithDelayExecutionA structure PagingWithDelayExecution parameterized by page type α with decidable equality and cache capacity k : ℕ, consisting of the…
- 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_payment_accountingFor all natural numbers k, P, and F_opt, every real number D_opt, and all natural numbers phi_0 and phi_final, if phi_0 = 0 and (P : ℝ) +…
Read back from the Lean
Given a type α with decidable equality, a natural number k, and an execution exec of type PagingWithDelayExecution α k, the algorithm cost paging_with_delay_alg_cost exec is less than or equal to (2 * (k : ℝ) + 2) * paging_with_delay_opt_cost exec.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes the $(2k+2)$-competitiveness of 1-FIFO for paging with delay by unfolding the cost definitions into the execution parameters and invoking the accounting invariant packaged inside the execution structure. Since the algorithm cost is $2P$, the optimal cost is $F_{\mathrm{opt}} + D_{\mathrm{opt}}$, and the execution's accounting invariant guarantees $P \le (k+1)(F_{\mathrm{opt}} + D_{\mathrm{opt}})$, multiplying this inequality by 2 immediately yields the desired bound.
The goal is rewritten in terms of the execution parameters $P$, $F_{\\mathrm{opt}}$, and $D_{\\mathrm{opt}}$, and the execution's accounting invariant is brought into scope.
Unfolding `paging_with_delay_alg_cost` (defined as $2P$) and `paging_with_delay_opt_cost` (defined as $F_{\\mathrm{opt}} + D_{\\mathrm{opt}}$) reduces the inequality to $2P \\le (2k + 2)(F_{\\mathrm{opt}} + D_{\\mathrm{opt}})$. We then obtain hypothesis $h$ from the execution's accounting property `exec.h_accounting`, which asserts that $P \\le (k + 1)(F_{\\mathrm{opt}} + D_{\\mathrm{opt}})$.
unfold paging_with_delay_alg_cost paging_with_delay_opt_cost have h := exec.h_accounting
The 1-FIFO algorithm cost is at most $2k + 2$ times the optimal offline cost. automation
Multiplying the accounting inequality $P \\le (k + 1)(F_{\\mathrm{opt}} + D_{\\mathrm{opt}})$ by 2 directly yields $2P \\le (2k + 2)(F_{\\mathrm{opt}} + D_{\\mathrm{opt}})$, which is closed by linear arithmetic over the reals.
linarith
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Strict (2k+2)-competitiveness of 1-FIFO for paging with delay (Theorem 1.2). -/theorem one_fifo_strictly_competitive_paging_with_delay {α : Type*} [DecidableEq α] {k : ℕ} (exec : PagingWithDelayExecution α k) : paging_with_delay_alg_cost exec ≤ (2 * (k : ℝ) + 2) * paging_with_delay_opt_cost exec := by unfold paging_with_delay_alg_cost paging_with_delay_opt_cost have h := exec.h_accounting linarith