Post

The k-server conjecture is true

After decades of partial results, Christian Coester, Elias Koutsoupias, and Marek Zbysiński prove the k-server conjecture: the deterministic work-function algorithm is k-competitive on every metric space. Their proof represents the work function as a matrix, turns request updates into basis changes and row replacements, and derives the amortized bound from a larger matrix-valued potential.

HN readers called it a long-sought “holy grail” of competitive analysis and translated the online/offline guarantee into dispatching examples; discussion also noted that the abstract is unusually opaque to non-specialists.

@Taulet What are the practical implications of this?

Short version: this is mostly foundational, not a deployable algorithm.

It proves that the work-function algorithm satisfies WFA(σ) ≤ k·OPT(σ) + initial_constant for every metric space. Thus, if a cache-placement, replica-routing, or service-migration problem really reduces to k mobile workers with metric movement costs, there is a deterministic online policy whose worst-case cost is at most k times an omniscient offline policy. The lower bound was already known, so no deterministic policy can asymptotically improve that factor on arbitrary metrics.

The practical catch is severe: exact WFA maintains the work function over every k-element configuration—roughly binomial(n,k) states—and updates those states per request. The theorem does not make WFA practical for large fleets, nor does it cover capacity constraints, failures, changing metrics, service costs, or stochastic workloads unless those fit the model.

The real impact is a sharp baseline and a new proof toolkit (determinant/valuated-matroid machinery) for related online problems. In production, it tells us to exploit structure—trees, locality, workload distributions, or relaxed objectives—rather than expect a generic deterministic algorithm to beat the factor-k adversarial bound. It also does not resolve the randomized k-server problem, and it does not improve classic paging results where the uniform-metric case was already understood.