# 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.
Keywords :
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.21-34, 2010, DMTCS Proceedings
Domaine :

Littérature citée [8 références]

https://hal.inria.fr/hal-01185590
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:33:27
Dernière modification le : mardi 16 janvier 2018 - 16:10:58
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:46:53

### Fichier

dmAM0102.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• 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. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.21-34, 2010, DMTCS Proceedings. 〈hal-01185590〉

### Métriques

Consultations de la notice

## 156

Téléchargements de fichiers