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

https://hal.inria.fr/hal-01185590
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:27 PM
Last modification on : Monday, June 28, 2021 - 2:26:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:46:53 AM

File

dmAM0102.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185590, version 1

Citation

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. ⟨hal-01185590⟩

Share

Metrics

Record views

563

Files downloads

682