Skip to Main content Skip to Navigation
Conference papers

Stochastic Analysis of the $k$-Server Problem on the Circle

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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:33:27 PM
Last modification on : Wednesday, November 3, 2021 - 2:18:09 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:46:53 AM


Publisher files allowed on an open archive



Aris Anagnostopoulos, Clément Dombry, Nadine Guillotin-Plantard, Ioannis Kontoyiannis, Eli Upfal. Stochastic Analysis of the $k$-Server Problem on the Circle. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.21-34, ⟨10.46298/dmtcs.2791⟩. ⟨hal-01185590⟩



Record views


Files downloads