On the Rate of Convergence of the Power-of-Two-Choices to its Mean-Field Limit

Abstract

This paper studies the rate of convergence of the power-of-two-choices, a celebrated randomized load balancing algorithm for many-server queueing systems, to its mean field limit. The convergence to the mean-field limit has been proved in the literature, but the rate of convergence remained to be an open problem. This paper establishes that the sequence of stationary distributions, indexed by $M,$ the number of servers in the system, converges in mean-square to its mean-field limit with rate $O\left(\frac{(\log M{)}^3(\log \log M{)}^2}{M}\right).$

References in corpus (1)

• Stein's method for steady-state diffusion approximations of $M/Ph/n+M$ systems

Cited by in corpus (1)

• Load Balancing in the Non-Degenerate Slowdown Regime