Power-of- d Choices Load Balancing in the Sub-Halfin-Whitt Regime

This is the authors' abstract. We don't add key points for this paper.

We consider the load-balancing system under Poisson arrivals, exponential services, and homogeneous servers under the power-of-d choices routing algorithm, which chooses the queue with minimum length among d randomly sampled queues. We study this system in the sub-Halfin-Whitt regime. In particular, we consider a sequence of systems with n servers, where the arrival rate of the nth system is [Formula: see text] for [Formula: see text]. It was shown that under power-of-d choices routing with [Formula: see text], the queue length behaves similarly to that of joining the shortest queue and that there are asymptotically zero queueing delays. The focus of this paper is to characterize the behavior when d is below this threshold. We obtain high probability bounds on the queue lengths for various values of d and large enough n. In particular, we show that when d is [Formula: see text] for some integer [Formula: see text], then the asymptotic queue length is m with high probability. Moreover, if d grows poly-log in n, that is, slower than any polynomial, but is at least [Formula: see text], the queue length blows up to infinity asymptotically. We obtain these results by using an iterative state space collapse approach. Funding: This work was partially supported by the National Science Foundation [Grants EPCN-2144316 and CMMI-2140534].