AFTD Auto-Formalizing Theoretical Domains

one_fifo_strictly_competitive_paging_with_delay

theoremverifiedformalization

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.

  1. 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}})$.

    lines 3–4

      unfold paging_with_delay_alg_cost paging_with_delay_opt_cost
      have h := exec.h_accounting
  2. 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.

    line 5

      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

/-- 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
See it in the graphDiscuss this resultChallenge it