A load balancing system in the many-server heavy-traffic asymptotics

We study a load balancing system in the many-server heavy-traffic regime. We consider a system with N servers, where jobs arrive to the system according to a Poisson process and have an exponentially distributed size with mean 1. We parametrize the arrival rate so that the arrival rate per server is $$1-N^{-\alpha }$$ 1 - N - α , where $$\alpha >0$$ α > 0 is a parameter that represents how fast the load grows with respect to the number of servers. The many-server heavy-traffic regime corresponds to the limit as $$N\rightarrow \infty $$ N → ∞ , and subsumes several regimes, such as the Halfin–Whitt regime ( $$\alpha =1/2$$ α = 1 / 2 ), the NDS regime ( $$\alpha =1$$ α = 1 ), as $$\alpha \downarrow 0$$ α ↓ 0 it approximates mean field and as $$\alpha \rightarrow \infty $$ α → ∞ it approximates the classical heavy-traffic regime. Most of the prior work focuses on regimes with $$\alpha \in [0,1]$$ α ∈ [ 0 , 1 ] . In this paper, we focus on the case when $$\alpha >1$$ α > 1 and the routing algorithm is power-of-d choices with $$d=\lceil cN^\beta \rceil $$ d = ⌈ c N β ⌉ for some constants $$c>0$$ c > 0 and $$\beta \ge 0$$ β ≥ 0 . We prove that $$\alpha +\beta >3$$ α + β > 3 is sufficient to observe that the average queue length scaled by $$N^{1-\alpha }$$ N 1 - α converges to an exponential random variable. In other words, if $$\alpha +\beta >3$$ α + β > 3 , the scaled average queue length behaves similarly to the classical heavy-traffic regime. In particular, this result implies that if d is constant, we require $$\alpha >3$$ α > 3 and if routing occurs according to JSQ we require $$\alpha >2$$ α > 2 . We provide two proofs to our result: one based on the Transform method introduced in Hurtado-Lange and Maguluri (Stoch Syst 10(4):275–309, 2020) and one based on Stein’s method. In the second proof, we also compute the rate of convergence in Wasserstein’s distance. In both cases, we additionally compute the rate of convergence in expected value. All of our proofs are powered by state space collapse.