the k-server problem

Imagine a city with k mobile repair vans. Trouble calls come in one at a time, each at some address; when a call arrives you must send one of your vans to that address, paying the distance it drives. You cannot see future calls, and once a van has moved you cannot un-drive it. Where you leave each van after a call shapes how expensive the next call will be. The k-server problem asks: how should you dispatch vans, online, to keep total driving distance small compared to a dispatcher who knew every call in advance?

Formally, you have k servers (points) living in a metric space — any setting with sensible distances, like a road map or even a line. A sequence of request points arrives; for each request you must move some server onto that point, paying the distance moved, and you keep doing this forever. The cost is the total distance all servers travel. This single framework is astonishingly general: paging is exactly the k-server problem on a special metric (the 'uniform' metric, where every page is distance 1 from every other), so caching is a baby case of k-server. The famous k-server conjecture says some deterministic online algorithm is k-competitive on every metric; it is proven for many cases (and the Work Function Algorithm is (2k-1)-competitive in general), but a clean k for all metrics remains one of the field's celebrated open challenges.

The k-server problem matters as the grand generalization that unifies many online movement-and-placement tasks: caching, scheduling delivery robots, managing data replicas across servers, even modeling memory hierarchies. It is a workhorse for testing what online algorithms can and cannot achieve, and a place where deep techniques (potential functions, work functions) were forged. The honest caveats: the full k-server conjecture is still open after decades; the best general guarantee, (2k-1)-competitive, is not known to be tight; and 'metric space' is doing real work — the guarantees rely on distances satisfying the triangle inequality.