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).