Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The deterministic kkk-server conjecture

Proved
KServer.kserver_conjecture

by Shuze Chen · Aug 22, 2026 · Mathlib c5ea003 (Lean v4.30.0)

competitive-analysisk-serveronline-algorithmsopen-problem

The kkk-server conjecture (Manasse--McGeoch--Sleator, 1990). For every k≥1k \ge 1k≥1, every metric space MMM, and every initial configuration C0C_0C0​ of kkk servers, there exists a deterministic online kkk-server algorithm AAA with initial configuration C0C_0C0​ that is kkk-competitive: for some constant aaa (independent of the request sequence),

costA(σ)  ≤  k⋅OPT(C0,σ)+afor every request sequence σ.\mathrm{cost}_A(\sigma) \;\le\; k \cdot \mathrm{OPT}(C_0, \sigma) + a \qquad \text{for every request sequence } \sigma.costA​(σ)≤k⋅OPT(C0​,σ)+afor every request sequence σ.

The matching lower bound is known (no ratio below kkk is achievable on any space with more than kkk points), so the conjecture asserts that the trivial lower bound is tight for every metric space. The best proven general upper bound is 2k−12k-12k−1 (Koutsoupias--Papadimitriou, 1995). This is the central open problem of competitive analysis.

Preamble
import Mathlib
import Definitions.Def_KServer_model
Formal statement
namespace KServer

theorem kserver_conjecture (k : ℕ) (hk : 1 ≤ k) (M : Type) [MetricSpace M]
    (C₀ : Config k M) :
    ∃ A : OnlineAlgorithm k M, A.conf [] = C₀ ∧ IsCompetitive A (k : ℝ) := by sorry

end KServer
Source
Posed in Manasse--McGeoch--Sleator, Competitive algorithms for server problems, J. Algorithms 11 (1990) 208-230, Section 8 (Open problems), for finite symmetric spaces; stated in the modern form formalized here (every metric space) as Conjecture 1.1 in Koutsoupias--Papadimitriou, On the k-server conjecture, J. ACM 42(5) (1995), https://doi.org/10.1145/210118.210128
Read-back

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

Read-back: kserver_conjecture

For every natural number kkk with k≥1k \ge 1k≥1, every metric space MMM (an arbitrary type equipped with a metric-space structure), and every initial configuration C0C_0C0​ — where a configuration of kkk servers in MMM is simply a function assigning to each index i∈{0,…,k−1}i \in \{0, \dots, k-1\}i∈{0,…,k−1} a point C0(i)∈MC_0(i) \in MC0​(i)∈M (servers are labeled, and distinct servers may occupy the same point) — the theorem asserts the existence of a deterministic online kkk-server algorithm AAA on MMM such that:

  1. AAA's configuration on the empty request sequence equals C0C_0C0​ (i.e. AAA starts at C0C_0C0​), and
  2. AAA is kkk-competitive (with kkk cast to a real number), in the sense unfolded below.

What an algorithm is here. An algorithm AAA consists of a map confA\mathrm{conf}_AconfA​ assigning to each finite sequence (list) lll of points of MMM a configuration confA(l):{0,…,k−1}→M\mathrm{conf}_A(l) : \{0,\dots,k-1\} \to MconfA​(l):{0,…,k−1}→M, together with the requirement that for every list lll and every point r∈Mr \in Mr∈M, some server index iii satisfies confA(l+ ⁣ ⁣+[r])(i)=r\mathrm{conf}_A(l \mathbin{+\!\!+} [r])(i) = rconfA​(l++[r])(i)=r — that is, after any request sequence ending in rrr, at least one server sits exactly at the point rrr. Since the configuration is a function of the request prefix alone, the algorithm is deterministic and cannot depend on future requests. The serving condition is imposed on all lists lll, not only prefixes of some fixed sequence.

Cost of the algorithm. For a request sequence σ=(r0,…,rn−1)\sigma = (r_0, \dots, r_{n-1})σ=(r0​,…,rn−1​) (a list of points of MMM, possibly empty), the cost of AAA is

costA(σ)  =  ∑j=0n−1∑i=0k−1d(confA(σ<j)(i),  confA(σ<j+1)(i)),\mathrm{cost}_A(\sigma) \;=\; \sum_{j=0}^{n-1} \sum_{i=0}^{k-1} d\bigl(\mathrm{conf}_A(\sigma_{<j})(i),\; \mathrm{conf}_A(\sigma_{<j+1})(i)\bigr),costA​(σ)=j=0∑n−1​i=0∑k−1​d(confA​(σ<j​)(i),confA​(σ<j+1​)(i)),

where σ<j\sigma_{<j}σ<j​ denotes the prefix of σ\sigmaσ of length jjj and the inner sum is the movement cost between two configurations: the sum over the kkk labeled servers of the distance each server iii travels between its positions in the two configurations (servers are matched by label, not optimally re-matched). For σ\sigmaσ empty the cost is 000.

Optimal offline cost. An (offline) schedule is a function SSS from N\mathbb{N}N to configurations. The schedule SSS serves σ\sigmaσ from C0C_0C0​ if S(0)=C0S(0) = C_0S(0)=C0​ and, for each index jjj with 0≤j<n0 \le j < n0≤j<n, some server iii satisfies S(j+1)(i)=rjS(j+1)(i) = r_jS(j+1)(i)=rj​ (values of SSS beyond nnn are unconstrained). The offline cost is

OPT(C0,σ)  =  inf⁡{ ∑j=0n−1∑i=0k−1d(S(j)(i), S(j+1)(i))  ∣  S serves σ from C0 },\mathrm{OPT}(C_0, \sigma) \;=\; \inf\Bigl\{\, \sum_{j=0}^{n-1} \sum_{i=0}^{k-1} d\bigl(S(j)(i),\, S(j+1)(i)\bigr) \;\Bigm|\; S \text{ serves } \sigma \text{ from } C_0 \,\Bigr\},OPT(C0​,σ)=inf{j=0∑n−1​i=0∑k−1​d(S(j)(i),S(j+1)(i))​S serves σ from C0​},

the infimum being the real-number infimum. (By the total-function convention for the real infimum, if the set of achievable costs were empty or unbounded below this infimum would default to 000; here each achievable cost is a sum of distances, hence ≥0\ge 0≥0, and with k≥1k \ge 1k≥1 a serving schedule always exists, so the set is a nonempty set of nonnegative reals.)

ccc-competitiveness. The algorithm AAA is ccc-competitive (here with c=kc = kc=k) if there exists a real constant aaa — quantified after AAA, so it may depend on AAA, on MMM, and on the initial configuration, but not on the request sequence; and it is not required to be nonnegative — such that for every request sequence σ\sigmaσ (including the empty one):

costA(σ)  ≤  c⋅OPT(confA([ ]), σ)  +  a,\mathrm{cost}_A(\sigma) \;\le\; c \cdot \mathrm{OPT}(\mathrm{conf}_A([\,]),\, \sigma) \;+\; a,costA​(σ)≤c⋅OPT(confA​([]),σ)+a,

where the offline cost is measured from AAA's own initial configuration confA([ ])\mathrm{conf}_A([\,])confA​([]) — which, by clause 1, equals C0C_0C0​. The inequality is non-strict (≤\le≤).

In summary: for every k≥1k \ge 1k≥1, every metric space MMM, and every starting placement of kkk labeled servers, there exists a deterministic online algorithm, starting from that placement and always ending each step with a server exactly on the newest request, whose total labeled-server movement cost on every request sequence is at most kkk times the optimal offline movement cost (an infimum over all schedules serving the sequence from the same start) plus an additive constant independent of the request sequence.

Human review
  • Endorsed by ShouqiaoWang · Aug 25, 2026

  • Endorsed by Shuze Chen · Aug 25, 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