Optimal-order randomized k-server on arbitrary metrics

← All digests

Family 110 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

A cache, a fleet of service vehicles, and a collection of movable resources share a basic difficulty: each request must be handled before the next request is known. Family 110 claims an optimal-order guarantee for a general mathematical model of this situation. A companion turns the existence result into a computable policy on finite rational inputs, with an important qualification about its initial cost.

1. The question

There are $k$ servers in a metric space. A request specifies a point, and a server must move there unless one is already present. The algorithm pays the distance traveled. It knows past requests but not future ones.

A greedy rule might always move the nearest server. But preserving a slightly farther server for an imminent request can be better, and the online algorithm cannot know that request is coming. The natural benchmark is an offline optimum that sees the whole sequence in advance.

How much more movement must an online policy pay? Randomization can help by preventing a fixed request sequence from exploiting one predictable pattern of decisions. The manuscripts claim a guarantee of order $\log^2(k+1)$ on every metric, independent of the number of locations or their geometric arrangement.

2. Background and essential definitions

Metrics and configurations

A metric $d(x,y)$ is a distance function: distances are nonnegative, symmetric, zero exactly when the points agree, and satisfy the triangle inequality. The latter says a detour cannot be shorter than the direct distance.

A configuration lists the positions of all $k$ labeled servers. Different servers may start at the same point. At each request, the stated model chooses one server to move directly to the requested location, leaving the others fixed. A zero-length move is allowed.

For a finite request sequence $\sigma$, let $\operatorname{OPT}(\sigma)$ be the least movement cost attainable with advance knowledge of the sequence, starting from the same initial configuration.

Competitive analysis

A randomized policy $A$ has competitive ratio $R$ if

$$\mathbb E[\operatorname{cost}_A(\sigma)]\le R\operatorname{OPT}(\sigma)+B$$

for every allowed request sequence. The expectation is over the policy’s random choices. The additive constant $B$ may depend on the fixed instance and initial configuration, but must not depend on the sequence or its length.

The term $B$ can absorb an initial disadvantage. It cannot absorb losses that continue growing faster than the optimum over arbitrarily long sequences. Nevertheless, a very large $B$ can make an asymptotic guarantee uninformative for ordinary finite workloads.

What the adversary knows

The request sequence is oblivious: it is fixed independently of the algorithm’s random bits. It may be chosen with full knowledge of the policy, but cannot adapt to the realized random choices.

An adversary that watches the actual server positions and chooses the next request accordingly is stronger. The family does not assert the same guarantee in that model.

Paging as an example

When every pair of distinct points has distance one, servers represent pages currently held in a cache. A request to a missing page costs one move; choosing a server corresponds to choosing which cached page to evict. General metrics allow different replacement costs and much richer geometry.

3. Development history and previous partial results

Manasse, McGeoch, and Sleator introduced the $k$-server framework and its competitive viewpoint. For deterministic policies, the classical lower bound is $k$ on metrics with more than $k$ points. Koutsoupias and Papadimitriou proved a $2k-1$ guarantee for the work function algorithm.

Randomized paging suggested a much smaller scale. Fiat and collaborators obtained logarithmic guarantees, and McGeoch and Sleator attained the harmonic ratio

$$H_k=1+\frac12+\cdots+\frac1k.$$

Since $H_k$ grows like $\log k$, it was tempting to expect a logarithmic ratio on every metric.

The history took a different turn: Bubeck, Coester, and Rabani established metrics requiring order $\log^2 k$. As explained and cited in M1, this disproved the original randomized logarithmic conjecture. A matching universal upper bound would therefore settle the revised worst-case scale, not confirm the old conjecture.

A major upper-bound approach approximates a metric by hierarchical trees. Such trees group nearby points at successively larger distance scales. Fakcharoenphol, Rao, and Talwar proved an expected distortion of order $\log n$ for an $n$-point metric.

Randomized server algorithms on these trees improved substantially, including squared-logarithmic dependence on $k$. But transferring a tree guarantee through a static embedding typically introduced another factor depending on $n$. That fails to give a bound depending on the server count alone.

M1 discusses dynamic embeddings and partition methods as predecessors, while explicitly distinguishing its argument from a withdrawn general guarantee in earlier work. M2 compares its implementation with stronger per-request time and random-bit guarantees available for tree-based algorithms whose general-metric ratio still depends on $n$.

4. What the new manuscripts claim

M1 states that an absolute constant $C$ works for every metric with at least $k+1$ points and every $k\ge2$: one randomized online policy satisfies

$$\mathbb E[\operatorname{cost}_A(\sigma)] \le C\log^2(k+1)\operatorname{OPT}(\sigma)+B$$

for every finite oblivious sequence. The same policy serves all horizons. The metric may be infinite, unbounded, or nondiscrete. If the initial positions are distinct, the paper states that $B=0$ is possible.

This first result makes no computational-efficiency claim. M2 supplies a uniform randomized implementation when the metric is finite and all distances are rational.

Let $L$ be the complete binary input length, including the metric, server count, and initial positions. M2 claims polynomial preprocessing and, at request number $t$, at most

$$p\!\left(L+\lceil\log_2(t+1)\rceil\right)$$

bit operations for one fixed polynomial $p$. The bound holds for every reachable internal state. Only unbiased random bits are required.

The implementation retains the squared-logarithmic competitive ratio but permits an unrestricted finite additive movement constant. Its useful policy may activate only after an enormous initial number of requests. Polynomial preprocessing and per-request work therefore do not imply a practical startup period.

5. Why the advance matters

Importance: 4/5, provisional. The $k$-server problem is a central model of online decision-making. A ratio matching the known worst-case order across arbitrary metrics would identify the scale of the unavoidable cost of lacking future information.

The independence from the size and geometry of the metric is decisive. A bound containing $\log n$ can deteriorate as more possible locations are added even when the number of servers stays fixed. The claimed result makes the server count the controlling parameter.

The family also illustrates an important distinction in theoretical algorithms: existence, computability, and practical efficiency are different achievements. M1 addresses the universal policy; M2 gives a finite computation with formal time bounds, while its additive constant limits what that says about actual service quality over moderate horizons.

6. The main idea

Compare distributions without revealing the future

M1 first studies a finite probability distribution on request sequences. For each complete sequence, choose an offline optimum. At an intermediate time, consider the conditional distribution of that optimum’s server positions given only the revealed requests.

This distribution is a mathematical comparator, not information about the realized future handed to the online algorithm. The argument later converts guarantees for finite distributions into one policy working against all fixed sequences.

Allocate fractional servers across scales

A hierarchy partitions the metric at different distance scales. Instead of immediately choosing integer server positions, the construction maintains fractional amounts of server mass in subtrees. Rank-related constraints express which allocations can satisfy the service requirements.

Some mass may remain temporarily at internal tree vertices. This allows the allocation to change gradually when the conditional comparator changes, instead of repeatedly committing all resources to fine-scale locations.

The paper claims a logarithmic loss in allocating this mass. Its partition construction contributes another logarithm, while subsequent steps preserve their product.

Pay for moving the hierarchy too

Changing partitions can help adapt to requests, but it is not free. A representation of parked mass by a point in the original metric may move even when no mass crosses a tree edge.

The manuscript introduces potentials—quantities stored in the analysis whose decreases can pay for movement—to account for partition edits and this additional travel. A rounding procedure then turns fractional mass into exactly $k$ actual servers with only a constant-factor loss.

Finally, finite minimax and compactness arguments produce a single policy for all finite histories, including on arbitrary infinite metrics. These are existence tools rather than an efficient recipe for computing probabilities.

The companion’s delayed construction

M2 replaces finite-horizon policy probabilities by rational transition tables satisfying linear constraints. It filters requests and organizes resets so a bounded table can support arbitrarily long service.

Constructing the table may take an uncontrolled but finite amount of time. At request $t$, the implementation simulates only a budget proportional to the binary length of $t$. Until construction finishes, it uses a simple fallback service. The total cost before activation is finite and is absorbed into $B$.

This explains both the formal per-request polynomial bound and its limitation: a finite constant can hide an exceptionally long initial phase.

7. Scope, limitations, and open questions

The squared-logarithmic order is a worst-case statement over metrics. It does not mean every metric requires that ratio; paging already shows better behavior in a special geometry.

The guarantee is in expectation against oblivious requests. It is not a pathwise movement guarantee or a guarantee against an adversary reacting to the realized random choices.

On arbitrary spaces, M1 asserts existence without effective access assumptions. M2 requires an explicit finite rational metric. Its additive constant, activation time, and dependence on the request-counter length leave room for stronger computational results with usable initialization and uniform practical bounds.

8. Sources and further reading

M1 contains the metric-independent existence theorem and the historical lower-bound comparison. M2 should be read alongside it: its introduction explains why the computational statement allows a large additive loss and a delayed transition to the constructed policy.

Source manuscripts

• M1. OpenAI, Squared-logarithmic randomized k-server on arbitrary metrics (September 24, 2026).
• M2. OpenAI, Uniform computation of the squared-logarithmic k-server bound (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.