# The Randomized k-Server Conjecture is False!

arXiv: https://arxiv.org/abs/2211.05753 · HTML: https://mlsanity.com/paper/2211.05753/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2022.

## Built on by (most cited first, 8 of 8)

- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph](https://mlsanity.com/paper/2403.07748/) (2024)
- [Compressing Value Predictions for Learning-Augmented Metrical Task Systems](https://mlsanity.com/paper/2609.33580/) (2026)

## Abstract (arXiv)

We prove a few new lower bounds on the randomized competitive ratio for the k-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987). More concretely, we show: 1. There exist (k+1)-point metric spaces in which the randomized competitive ratio for the k-server problem is Omega(log2 k). This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least k+1 points, the competitive ratio is Theta(log k). 2. Consequently, there exist n-point metric spaces in which the randomized competitive ratio for MTS is Omega(log2 n). This matches the upper bound that holds for all metrics. The previously best existential lower bound was Omega(log n) (which was known to be tight for some families of metrics). 3. For all k<n∈mathbb N, for *all* n-point metric spaces the randomized k-server competitive ratio is at least Omega(log k), and consequently the randomized MTS competitive ratio is at least Omega(log n). These universal lower bounds are asymptotically tight. The previous bounds were Omega(log k/loglog k) and Omega(log n/log log n), respectively. 4. The randomized competitive ratio for the w-set metrical service systems problem, and its equivalent width-w layered graph traversal problem, is Omega(w2). This slightly improves the previous lower bound and matches the recently discovered upper bound. 5. Our results imply improved lower bounds for other problems like k-taxi, distributed paging and metric allocation. These lower bounds share a common thread, and other than the third bound, also a common construction.