Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The marking algorithm is 2Hk2H_k2Hk​-competitive for paging (Theorem 1)

Proved
CompetitivePaging.Marking.marking_competitive

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysisk-serveronline-algorithmsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1pagingrandomized-algorithms

Let MMM be a set of nnn vertices with the uniform metric (distinct vertices at distance 111), enumerated as e(0),…,e(n−1)e(0), \dots, e(n-1)e(0),…,e(n−1), and let 1≤k≤n1 \le k \le n1≤k≤n. Run the marking algorithm with kkk servers, initially on e(0),…,e(k−1)e(0), \dots, e(k-1)e(0),…,e(k−1), and let CM(σ)C_M(\sigma)CM​(σ) be its expected cost (expected number of server moves) on a finite request sequence σ\sigmaσ. Let OPT(σ)\mathrm{OPT}(\sigma)OPT(σ) be the optimal off-line cost of serving σ\sigmaσ with kkk servers starting from the same initial configuration C0C_0C0​. With Hk=1+12+⋯+1kH_k = 1 + \frac12 + \dots + \frac1kHk​=1+21​+⋯+k1​, there is a constant aaa such that for every request sequence σ\sigmaσ,

CM(σ)≤2Hk⋅OPT(σ)+a.C_M(\sigma) \le 2H_k \cdot \mathrm{OPT}(\sigma) + a.CM​(σ)≤2Hk​⋅OPT(σ)+a.

That is, the marking algorithm is a 2Hk2H_k2Hk​-competitive algorithm for the uniform kkk-server problem on nnn vertices, which is the paging problem with a cache of kkk pages and nnn pages of address space. Since Hk≈ln⁡kH_k \approx \ln kHk​≈lnk, this is exponentially better than the factor kkk that no deterministic on-line algorithm can beat.

Formalization Note. The constant aaa is quantified before σ\sigmaσ. The paper compares with every algorithm BBB; the optimal off-line cost from C0C_0C0​ is the infimum of these costs up to the choice of BBB's starting configuration, which changes the cost by at most kkk and is absorbed into aaa.

Preamble
import Mathlib
import Definitions.Def_KServer_model
import Definitions.Def_CompetitivePaging_Marking_markingAlgorithm
Formal statement
namespace CompetitivePaging.Marking

/-- Theorem 1 (p. 3): the marking algorithm is a `2 H_k`-competitive algorithm for the
uniform `k`-server problem on `n` vertices. -/
theorem marking_competitive {n k : ℕ} {M : Type*} [MetricSpace M] [DecidableEq M]
    (e : Fin n ≃ M) (hdist : ∀ x y : M, x ≠ y → dist x y = 1) (hk : 1 ≤ k) (hkn : k ≤ n) :
    ∃ a : ℝ, ∀ σ : List M,
      markingExpCost k (initVertices e hkn) σ
        ≤ 2 * (harmonic k : ℝ) * KServer.offlineCost (initConfig e hkn) σ + a := by sorry

end CompetitivePaging.Marking
Source
Fiat, Karp, Luby, McGeoch, Sleator, Young, Competitive Paging Algorithms, arXiv:cs/0205038v1, p. 3, Theorem 1; definition of c-competitive on p. 1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let nnn and kkk be natural numbers, and let MMM be a type with a metric ddd and decidable equality. Every argument of the theorem is listed here:

  • e:{0,1,…,n−1}→Me : \{0, 1, \dots, n-1\} \to Me:{0,1,…,n−1}→M is a bijection, so MMM has exactly nnn points. Each point is labelled by a unique index below nnn.
  • (uniform metric) For all x,y∈Mx, y \in Mx,y∈M with x≠yx \neq yx=y, d(x,y)=1d(x,y) = 1d(x,y)=1. Distinct points are always at distance exactly 111, and d(x,x)=0d(x,x) = 0d(x,x)=0 because ddd is a metric.
  • (server count) 1≤k1 \le k1≤k.
  • (capacity) k≤nk \le nk≤n. Call this hypothesis hknh_{kn}hkn​.

The statement uses four objects from the imported files. Their bodies are not part of the code under audit, so they are described only by what the statement shows about them:

  • IeI_{e}Ie​, written initVertices e hkn, is a starting set of vertices. It is built from the bijection eee and the fact k≤nk \le nk≤n, and it is the starting point for the marking algorithm.
  • CeC_{e}Ce​, written initConfig e hkn, is a starting configuration for the kkk-server problem, also built from eee and k≤nk \le nk≤n.
  • Markk(Ie,σ)\mathrm{Mark}_k(I_e, \sigma)Markk​(Ie​,σ), written markingExpCost k (initVertices e hkn) σ, is a real number. By its name it is the expected cost of the marking algorithm with parameter kkk, started from IeI_eIe​ and serving the request sequence σ\sigmaσ.
  • OPT(Ce,σ)\mathrm{OPT}(C_e, \sigma)OPT(Ce​,σ), written KServer.offlineCost (initConfig e hkn) σ, is a real number. By its name it is the offline cost of serving σ\sigmaσ from the configuration CeC_eCe​ in the kkk-server model.

The statement does not show whether these objects use the metric ddd, the number kkk or the bijection eee in any particular way. Those details are fixed by the imported definitions.

Hk=∑i=1k1iH_k = \sum_{i=1}^{k} \frac{1}{i}Hk​=∑i=1k​i1​ is the kkk-th harmonic number, a rational number treated here as a real number.

Conclusion. There is a real constant aaa that satisfies the inequality below for every finite list σ=(σ1,…,σm)\sigma = (\sigma_1, \dots, \sigma_m)σ=(σ1​,…,σm​) of points of MMM, including the empty list:

Markk(Ie,σ)  ≤  2Hk⋅OPT(Ce,σ)+a.\mathrm{Mark}_k(I_e, \sigma) \;\le\; 2 H_k \cdot \mathrm{OPT}(C_e, \sigma) + a.Markk​(Ie​,σ)≤2Hk​⋅OPT(Ce​,σ)+a.
  • aaa may depend on nnn, kkk, MMM, its metric, eee and the hypotheses, but not on σ\sigmaσ.
  • aaa can have any sign, and no bound is placed on its size.
  • The inequality is non-strict.
  • The statement does not say that the multiplier 2Hk2H_k2Hk​ is the best possible.
  • Nothing is said about sequences that are not lists of points of MMM, and nothing is said about starting configurations other than IeI_eIe​ and CeC_eCe​.

Degenerate cases. Because 1≤k≤n1 \le k \le n1≤k≤n, n≥1n \ge 1n≥1 and MMM is nonempty. n=0n = 0n=0 and k=0k = 0k=0 are excluded, so HkH_kHk​ never involves division by zero.

  • n=1n = 1n=1: Then k=1k = 1k=1 and MMM has exactly one point. The uniform-metric hypothesis holds vacuously, H1=1H_1 = 1H1​=1, and the claim is Mark1(Ie,σ)≤2 OPT(Ce,σ)+a\mathrm{Mark}_1(I_e,\sigma) \le 2\,\mathrm{OPT}(C_e,\sigma) + aMark1​(Ie​,σ)≤2OPT(Ce​,σ)+a for all σ\sigmaσ, where every entry of σ\sigmaσ is the single point.
  • k=nk = nk=n: This is permitted, and then the number of servers equals the number of points.
  • k=1k = 1k=1 with n>1n > 1n>1: The multiplier is 222.
  • Empty list σ\sigmaσ: The claim only requires Markk(Ie,[ ])≤2Hk OPT(Ce,[ ])+a\mathrm{Mark}_k(I_e,[\,]) \le 2H_k\,\mathrm{OPT}(C_e,[\,]) + aMarkk​(Ie​,[])≤2Hk​OPT(Ce​,[])+a, which any large enough aaa satisfies.
  • Satisfiability: The hypotheses can all be met together, for example with M={0,…,n−1}M = \{0,\dots,n-1\}M={0,…,n−1} and the discrete metric, so the theorem is not vacuous.
  • When the conclusion is trivial: Because aaa is chosen before σ\sigmaσ and may be arbitrarily large, the conclusion holds automatically whenever Markk(Ie,σ)−2Hk OPT(Ce,σ)\mathrm{Mark}_k(I_e,\sigma) - 2H_k\,\mathrm{OPT}(C_e,\sigma)Markk​(Ie​,σ)−2Hk​OPT(Ce​,σ) is bounded above over all σ\sigmaσ. Whether that happens trivially depends on the imported definitions and is not visible here.
  • Default values: Whether the imported definitions ever return a default value (for example an expectation of something non-integrable, subtraction of natural numbers, or division by zero) is also not visible here.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me