In the ** k-server problem ** we are given a metric
space M in which there reside k identical mobile ** servers **.
A sequence of ** requests ** is received. When each request
is received, at a point r in M, one (it does not matter which one) of
the servers must move to r. This constitutes ** servicing **
the request.

The ** online ** condition is that no request is known until
all prior requests are serviced. The goal is to minimize cost, defined
as the total distance moved by all servers while servicing the request
sequence.

An offline ** optimal ** algorithm can minimize cost by
using dynamic programming. But, even for fairly simple examples, it
can be shown that no online algorithm can be optimal.

It is traditional to measure the goodness of an online algorithm by
its ** competitiveness **, a real number C > 1.
We say that an online algorithm is ** C-competitive **
if, for any request sequence, the cost incurred by the algorithm
is at most C times the optimal cost of servicing that same sequence,
plus O(1).

For the k-server problem, there is a known lower bound of k on the competitiveness. The case k = 1 is trivial. For k = 2, the problem is solved, that is, there are 2-competitive algorithms known. For k > 2, the best known competitiveness is (2k-1).