Stochastic Analysis of the k-Server Problem on the Circle
A. Anagnostopoulos, C. Dombry, N. Guillotin-Plantard, I. Kontoyiannis, E. Upfal
Abstract
We consider a stochastic version of the k-server problem in which k servers move on a circle to satisfy stochastically generated requests. The requests are independent and identically distributed according to an arbitrary distribution on a circle, which is either discrete or continuous. The cost of serving a request is the distance that a server needs to move to reach the request. The goal is to minimize the steady-state expected cost induced by the requests. We study the performance of a greedy strategy, focusing, in particular, on its convergence properties and the interplay between the discrete and continuous versions of the process.
Full Text: PostScript PDF