Optimal-order randomized k-server on arbitrary metrics

The explanation

Picture three spots, A, B and C, each one mile from the other two. You run two repair vans, parked at A and B. Calls arrive one at a time. A van must drive to each called spot, and you pay for every mile. Say the calls run C, A, B, C, A, B, and so on, twelve calls in all. One simple rule sends the van whose spot was called longest ago. On this list it drives every single time, 12 miles in total. Someone who knew the whole list in advance would drive only 6.

This is the k-server problem, here with k = 2 servers (movable units, like the vans). An online rule (one that must act before seeing later calls) is judged by its competitive ratio. That is the worst factor by which its cost exceeds the best cost in hindsight. A fixed extra amount is allowed. Mark Manasse, Lyle McGeoch and Daniel Sleator introduced the problem. They showed that no fixed rule beats a ratio of k on a space with more than k points. The example hints why. Calls can always target the one empty spot.

Coin flips help. A rule that flips coins can hide its next move. The list of calls must then be fixed in advance, without seeing the coins. This setting is called an oblivious adversary. When all distances are equal, the problem is called paging. There, McGeoch and Sleator reached the best possible ratio, 1 + 1/2 + … + 1/k. For k = 100 that sum is about 5.19, against 100 for rules without coins. It grows like the natural logarithm of k (ln 100 is about 4.6). Many expected a logarithmic ratio on every space. That guess was the randomized k-server conjecture.

In 2023, Sébastien Bubeck, Christian Coester and Yuval Rabani disproved it. They built spaces with k + 1 points that force a ratio of order (log k)², the logarithm squared. So the squared logarithm is the best order one can hope for on every space. Upper bounds lagged behind. In 2015, Bansal, Buchbinder, Mądry and Naor gave the first bound in powers of logarithms for finite spaces. Its bound also grows with n, the number of points. In 2018, Bubeck, Cohen, Lee, Lee and Mądry reached (log k)² on special tree-shaped spaces. Carrying that to a general space costs an extra factor of log n. James Lee proposed trees that change as calls arrive, but his general claim was withdrawn after a gap.

The first paper proves a ratio of C times (log(k+1))² on every space, for one fixed number CSource 1. The same C works for every space and every k of at least 2. The space needs at least k + 1 points. It may be infinite, and its distances may be unboundedSource 2. For each space and starting position, one rule handles every finite list of calls. A fixed extra amount, B, is allowed, depending on the space and the start but not on the listSource 3. If the servers start at different points, B is zero.

The single difficulty was the size of the space. A fixed tree picture of a space distorts its distances by a factor that grows with n. The paper lets its grouping of points change as calls come inSource 4. It steers those changes by where a hidden best solution is likely to be. It then charges each change against real movement, so the changes stay affordable. One logarithm comes from the changing groups and one from sharing servers down the treeSource 5.

Return to the vans and scale up. The theorem does not say how large C is. So it does not promise beating a ratio of 100 at k = 100. Its force is in how slowly the bound grows. At k = 100, (ln 101)² is about 21.3. At k = 1,000, (ln 1,001)² is about 47.7. The number of servers grew tenfold, and that factor grew about 2.2-fold. The number of points, even infinitely many, no longer enters it.

The first paper does not claim its rule can be computed quicklySource 2. The second paper claims to fill part of that gap, for finite spaces with rational distances. It builds one algorithm whose setup time is polynomial (bounded by a fixed power) in the input's length in bitsSource 6. The time for call number t may also grow with the number of binary digits of t. The price sits in the extra amount B. It is finite but may be enormous. The algorithm may serve a huge number of early calls with one fixed server before its full rule takes overSource 7. Coester and Cosson had faster methods, but their ratio on general spaces keeps a log n factor.

How sure is this? A computer proof checker called Lean has checked formal versions of both main statements, according to the Lean scope note. They are the squared-logarithmic bound on every space and the computable algorithm on finite rational spaces. The note does not claim the extra amount B is polynomially bounded. No specialist review of either paper has been published.

What it doesn't show. This does not give the size of the constant C or a useful bound on the extra startup cost.