The k-Server Problem - The State of the Art

In online computation, an algorithm has to make decisions without knowledge of future inputs. Online problems occur naturally across the entire field of computer science.

The deterministic k-server problem is perhaps the most notorious problem in the area; its competitive ratio, which is conjectured to be k, has remained open for more than a decade. Perhaps more daunting than the deterministic server problem, is to determine the exact competitiveness of the randomized k-server problem. Even for k=2, this problem is unresolved. There are many interesting special cases of the server problem, such as the k-cache paging problem and the weighted server problem.

Various models of computation involve restrictions on the power of an algorithm. Recently, we have introduced the concept of "tracklessness" for the k server problem. Tracklessness is a property of an online algorithm which is a restriction on what input data the algorithm uses in its computation, and on what outputs the algorithm gives. We have shown that many known algorithms for the server problem are trackless, and that the k-server conjecture fails for trackless algorithms. On the positive side, analyzing the (non-trackless) work function algorithm, we have been able to settle the k-server conjecture for k=3 in the Manhattan plane.

For the randomized problem, we have introduced the novel concept of knowledge states. We have used optimization techniques to construct a non-trivial knowledge state algorithm for the 2-server problem on the line with competitive ratio less than 2. We conjecture that a knowledge state algorithm with competitive ratio less than 2 exists for general spaces.

B.Hammer