# Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 May 2022.

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

- [k-server-bench: Automating Potential Discovery for the k-Server Conjecture](https://mlsanity.com/paper/2604.07240/) (2026)

## Abstract (arXiv)

The deterministic k-server conjecture states that there is a k-competitive deterministic algorithm for the k-server problem for any metric space. We show that the work function algorithm is 3-competitive for the 3-server problem on circle metrics, a case left open by Coester and Koutsoupias (2021). Our analysis follows the existing framework but introduces a new potential function which may be viewed as a relaxation of the counterpart by Coester and Koutsoupias (2021). We further notice that the new potential function and many existing ones can be rewritten in a canonical form. Through a computer-aided verification, however, we find that no such canonical potential function can resolve the deterministic 3-server conjecture for general metric spaces under the current analysis framework.