Universality of load balancing schemes on the diffusion scale

We consider a system of N parallel queues with identical exponential service rates and a single dispatcher where tasks arrive as a Poisson process. When a task arrives, the dispatcher always assigns it to an idle server, if there is any, and to a server with the shortest queue among d randomly selected servers otherwise (1≤ d ≤ N ). This load balancing scheme subsumes the so-called join-the-idle queue policy ( d =1) and the celebrated join-the-shortest queue policy ( d = N ) as two crucial special cases. We develop a stochastic coupling construction to obtain the diffusion limit of the queue process in the Halfin‒Whitt heavy-traffic regime, and establish that it does not depend on the value of d , implying that assigning tasks to idle servers is sufficient for diffusion level optimality.