On the maximum queue length in the supermarket model (Q2496955)

The paper studies a well-known queueing model with \(n\) separate queues, each with a single server. Customers arrive into the system in a Poisson process at rate \(\lambda n\), where \(0 < \lambda < 1\). Upon arrival each customer chooses \(d \geq 2\) queues uniformly at random with replacement, and joins a shortest queue amongst those chosen (where she breaks ties by choosing the first of the shortest queues in the list of \(d\)). Customers are served according to the first-come-first-served discipline. Service times are independent exponentially distributed random variables with mean 1. It is shown that with probability tending to 1 as \(n \to \infty \), in the equilibrium distribution the maximum queue length takes at most two values, which are \(\ln \ln n/d + O(1)\). It is shown also that the system is rapidly mixing.