On the maximum queue length in the supermarket model

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

There are $n$ queues, each with a single server. Customers arrive in a Poisson process at rate $λn$, where $0<λ<1$. Upon arrival each customer selects $d\geq2$ servers uniformly at random, and joins the queue at a least-loaded server among those chosen. Service times are independent exponentially distributed random variables with mean 1. We show that the system is rapidly mixing, and then investigate the maximum length of a queue in the equilibrium distribution. We prove that with probability tending to 1 as $n\to\infty$ the maximum queue length takes at most two values, which are $\ln\ln n/\ln d+O(1)$.
Published at http://dx.doi.org/10.1214/00911790500000710 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Keywords

Probability, 60C05 (Primary) 68R05, 90B22, 60K25, 60K30, 68M20 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/112898

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0605639
 http://arxiv.org/abs/math/0605639
 Annals of Probability 2006, Vol. 34, No. 2, 493-527
 doi:10.1214/00911790500000710

Collections

arXiv