Deterministic $k$-server: no algorithm is $c$-competitive for $c<k$ on the uniform space with $k+1$ points

The competitive ratio of deterministic $k$-server algorithms is at least $k$.

Let $k \ge 1$ and let $M$ be the uniform metric space on $k+1$ points: $M$ has exactly $k+1$ elements (witnessed by a bijection $e : \{0,\dots,k\} \to M$) and any two distinct points of $M$ are at distance $1$. This is the paging metric space with $k$ pages of cache and $k+1$ distinct pages.

Then no deterministic online $k$-server algorithm on $M$ is $c$-competitive for any $c < k$: for every algorithm $A$ and every additive constant $a$ there is a request sequence $\sigma$ with

This is the classical lower bound of Manasse, McGeoch and Sleator: the adversary always requests the unique point not covered by the algorithm, so the algorithm pays $1$ per request, while an offline schedule that serves the requests in blocks of $k$ consecutive requests pays at most $n/k + k$ in total. It shows that the constant $k$ in the $k$-server conjecture is the smallest possible, so the conjecture — if true — is tight.