Stochastic Analysis of the $k$-Server Problem on the Circle
Aris Anagnostopoulos (1), Clément Dombry (2) (3), Nadine Guillotin-Plantard (4), Ioannis Kontoyiannis (5), Eli Upfal (6) (7)
(1) Department of Informatics and System Sciences
(2) Laboratoire de Mathématiques et Applications
(3) Laboratoire de mathématiques et applications [UMR 7348]
(4) Institut Camille Jordan
(5) Department of Informatics [Athens]
(6) Department of Computer Science
(7) Department of Computer Science [Providence]
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.
Keywords
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
