The Supermarket Model with Bounded Queue Lengths in Equilibrium

In the supermarket model, there are n queues, each with a single server. Customers arrive in a Poisson process with arrival rate λn, where λ = λ(n) ∈ (0, 1). Upon arrival, a customer selects d = d(n)servers uniformly at random, and joins the queue of a least-loaded server amongst those chosen. Service times are independent exponentially distributed randomvariables with mean 1. In this paper, we analyse the behaviour of the supermarket model inthe regime where λ(n) = 1 − n−α and d(n) = nβ, where α and β are fixed numbersin (0, 1]. For suitable pairs (α, β), our results imply that, in equilibrium, with probabilitytending to 1 as n → ∞, the proportion of queues with length equal to k = α/β is at least1−2n−α+(k−1)β , and there are no longer queues. We further show that the process is rapidlymixing when started in a good state, and give bounds on the speed of mixing for more generalinitial conditions.