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

2016/05/21 by Ying, Lei
#FOS: Computer and information sciences #FOS: Mathematics #Networking and Internet Architecture (cs.NI) #Probability (math.PR)

paper · doi:10.48550/arxiv.1605.06581

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(((log M)³ (loglog M)²)/(M)).

Related

• Convergence properties of many parallel servers under power-of-D load balancing
• Beyond Scaling: Calculable Error Bounds of the Power-of-Two-Choices Mean-Field Model in Heavy-Traffic
• Mean Waiting Time in Large-Scale and Critically Loaded Power of d Load Balancing Systems
• On the Power-of-d-choices with Least Loaded Server Selection
• Invariance principle and McKean-Vlasov limit for randomized load balancing in heavy traffic