On the maximum queue length in the supermarket model

Abstract

There are $n$ queues, each with a single server. Customers arrive in a Poisson process at rate $\lambda n$, where $0<\lambda <1$. Upon arrival each customer selects $d\ge 2$ 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)

References in corpus (1)

• On the power of two choices: Balls and bins in continuous time

Cited by in corpus (8)

• Scalable load balancing in networked systems: A survey of recent advances
• Universality of Power-of-$d$ Load Balancing in Many-Server Systems
• On the power of two choices: Balls and bins in continuous time
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• Supermarket Model on Graphs
• Choice-Driven Phase Transition in Complex Networks
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
• Balanced routing of random calls