The marking algorithm is -competitive for paging (Theorem 1)
ProvedCompetitivePaging.Marking.marking_competitiveLet be a set of vertices with the uniform metric (distinct vertices at distance ), enumerated as , and let . Run the marking algorithm with servers, initially on , and let be its expected cost (expected number of server moves) on a finite request sequence . Let be the optimal off-line cost of serving with servers starting from the same initial configuration . With , there is a constant such that for every request sequence ,
That is, the marking algorithm is a -competitive algorithm for the uniform -server problem on vertices, which is the paging problem with a cache of pages and pages of address space. Since , this is exponentially better than the factor that no deterministic on-line algorithm can beat.
Formalization Note. The constant is quantified before . The paper compares with every algorithm ; the optimal off-line cost from is the infimum of these costs up to the choice of 's starting configuration, which changes the cost by at most and is absorbed into .
import Mathlib import Definitions.Def_KServer_model import Definitions.Def_CompetitivePaging_Marking_markingAlgorithm
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let and be natural numbers, and let be a type with a metric and decidable equality. Every argument of the theorem is listed here:
- is a bijection, so has exactly points. Each point is labelled by a unique index below .
- (uniform metric) For all with , . Distinct points are always at distance exactly , and because is a metric.
- (server count) .
- (capacity) . Call this hypothesis .
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:
- , written
initVertices e hkn, is a starting set of vertices. It is built from the bijection and the fact , and it is the starting point for the marking algorithm. - , written
initConfig e hkn, is a starting configuration for the -server problem, also built from and . - , written
markingExpCost k (initVertices e hkn) σ, is a real number. By its name it is the expected cost of the marking algorithm with parameter , started from and serving the request sequence . - , written
KServer.offlineCost (initConfig e hkn) σ, is a real number. By its name it is the offline cost of serving from the configuration in the -server model.
The statement does not show whether these objects use the metric , the number or the bijection in any particular way. Those details are fixed by the imported definitions.
is the -th harmonic number, a rational number treated here as a real number.
Conclusion. There is a real constant that satisfies the inequality below for every finite list of points of , including the empty list:
- may depend on , , , its metric, and the hypotheses, but not on .
- 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 is the best possible.
- Nothing is said about sequences that are not lists of points of , and nothing is said about starting configurations other than and .
Degenerate cases. Because , and is nonempty. and are excluded, so never involves division by zero.
- : Then and has exactly one point. The uniform-metric hypothesis holds vacuously, , and the claim is for all , where every entry of is the single point.
- : This is permitted, and then the number of servers equals the number of points.
- with : The multiplier is .
- Empty list : The claim only requires , which any large enough satisfies.
- Satisfiability: The hypotheses can all be met together, for example with and the discrete metric, so the theorem is not vacuous.
- When the conclusion is trivial: Because is chosen before and may be arbitrarily large, the conclusion holds automatically whenever is bounded above over all . 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.