OAI.KServer.main_theorem

The theorem states that the randomized k-server problem has a polylogarithmic competitive ratio, in the form of the defined proposition MainStatement. A configuration of k servers is a function from Fin k to points of a space X, serving a request moves the server with a chosen label to the request point, and the service cost of a request sequence with a label sequence is the sum of the distances moved. A randomized policy sees the history of earlier (request, label) pairs and the current request, and returns a probability distribution over the k labels. The expected cost of a policy from a starting configuration s is the sum over all label sequences of the path probability times the service cost, and the optimal cost is the infimum of service cost over all label sequences. The statement asserts that there is a constant C>0, independent of k, X and s, such that for every integer k≥2 and every metric space X (in any universe u) admitting an injective map from Fin(k+1) (so X has at least k+1 points), and every starting configuration s, there exist a policy A and a constant B≥0, with B=0 whenever s is injective, such that for every finite request list the expected cost of A from s is at most C(log(k+1))² times the optimal cost plus B.