The Join-the-Shortest-Queue System in the Halfin-Whitt Regime: Rates of Convergence to the Diffusion Limit

References

• Atar R (2012) A diffusion regime with nondegenerate slowdown. Oper. Res. 60(2):490–500.Link, Google Scholar
• Banerjee S, Mukherjee D (2019) Join-the-shortest queue diffusion limit in Halfin-Whitt regime: Tail asymptotics and scaling of extrema. Ann. Appl. Probab. 29(2):1262–1309.Google Scholar
• Banerjee S, Mukherjee D (2020) Join-the-shortest Queue diffusion limit in Halfin-Whitt regime: Sensitivity on the heavy-traffic parameter. Ann. Appl. Probab. 30(1):80–144.Google Scholar
• Barbour AD (1988) Stein’s method and Poisson process convergence. J. Appl. Probab. 25:175–184.Google Scholar
• Barbour A (1990) Stein’s method for diffusion approximations. Probab. Theory Related Fields 84(3):297–322.Google Scholar
• Braverman A (2020) Steady-state analysis of the join the shortest queue model in the Halfin-Whitt regime. Math. Oper. Res. 45(3):1069–1103.Link, Google Scholar
• Braverman A (2022) The prelimit generator comparison approach of Stein’s method. Stochast. Systems 12(2):181–204.Link, Google Scholar
• Braverman A, Dai JG (2017) Stein’s method for steady-state diffusion approximations of M/Ph/n+M systems. Ann. of Appl. Probab. 27(1):550–581.Google Scholar
• Brown TC, Xia A (2001) Stein’s method and birth-death processes. Ann. Probab. 29(3):1373–1403.Google Scholar
• Cao P, He S, Huang J, Liu Y (2021) To pool or not to pool: Queueing design for large-scale service systems. Oper. Res. 69(6):1866–1885.Link, Google Scholar
• Erdogdu MA, Mackey L, Shamir O (2018) Global non-convex optimization with discretized diffusions. Preprint, submitted October 29, https://arxiv.org/abs/1810.12361v1.Google Scholar
• Eryilmaz A, Srikant R (2012) Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72(3-4):311–359.Google Scholar
• Eschenfeldt P, Gamarnik D (2018) Join the shortest queue with many servers: The heavy-traffic asymptotics. Math. Oper. Res. 43(3):867–886.Link, Google Scholar
• Fang X, Shao QM, Xu L (2018) Multivariate approximations in Wasserstein distance by Stein’s method and Bismut’s formula. Preprint, submitted January 24, https://arxiv.org/abs/1801.07815.Google Scholar
• Feller W (1968) An Introduction to Probability Theory and Its Applications, vol. I, 3rd ed. (John Wiley & Sons Inc., New York).Google Scholar
• Gast N (2017) Expected values estimated via mean-field approximation are 1/n-accurate. Proc. ACM Measurement Anal. Comput. Syst. 1(1):1–26.Google Scholar
• Gast N, Van Houdt B (2017) A refined mean field approximation. Proc. ACM Measurement Anal. Comput. Syst. 1(2):1–28.Google Scholar
• Gast N, Bortolussi L, Tribastone M (2019) Size expansions of mean field approximation: Transient and steady-state analysis. Performance Evaluation 129:60–80.Google Scholar
• Gaunt RE, Walton N (2020) Stein’s method for the single server queue in heavy traffic. Statist. Probab. Lett. 156:108566.Google Scholar
• Götze F (1991) On the rate of convergence in the multivariate CLT. Ann. Probab. 19(2):724–739.Google Scholar
• Gupta V, Walton N (2019) Load balancing in the nondegenerate slowdown regime. Oper. Res. 67(1):281–294.Link, Google Scholar
• Gurvich I (2014) Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. Ann. Appl. Probab. 24(6):2527–2559.Google Scholar
• Hairi LX, Ying L (2021) Beyond scaling: Calculable error bounds of the power-of-two-choices mean-field model in heavy-traffic. Proc. Twenty-Second Internat. Sympos. Theory, Algorithmic Foundations, Protocol Design Mobile Networks Mobile Comput. (Association for Computing Machinery, New York), 1–10.Google Scholar
• Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• Hurtado-Lange D, Maguluri ST (2022) A load balancing system in the many-server heavy-traffic asymptotics. Queueing Systems Theory Appl. 101(3–4):353–391.Google Scholar
• Jin X, Pang G, Xu L, Xu X (2022) An approximation to the invariant measure of the limiting diffusion of G/Ph/n+GI queues in the Halfin-Whitt regime and related asymptotics. Preprint, submitted September 15, https://arxiv.org/abs/2209.07361.Google Scholar
• Kallenberg O (2001) Foundations of Modern Probability, Springer Series in Statistics, Probability and Its Applications, 2nd ed. (Springer, New York).Google Scholar
• Liu X, Ying L (2019) A simple steady-state analysis of load balancing algorithms in the sub-halfin-whitt regime. SIGMETRICS Perform. Eval. Rev. 46(2):15–17.Google Scholar
• Liu X, Ying L (2020) Steady-state analysis of load-balancing algorithms in the Sub-Halfin-Whitt regime. J. Appl. Probab. 57(2):578–596.Google Scholar
• Liu X, Gong K, Ying L (2022) Steady-state analysis of load balancing with coxian-2 distributed service times. Naval Res. Logist. 69(1):57–75.Google Scholar
• Lu Y (2021) On a stein method based approximation for a two-dimensional Markov chain. Preprint, submitted June 6, https://arxiv.org/abs/2106.03145.Google Scholar
• Mackey L, Gorham J (2016) Multivariate Stein factors for a class of strongly log-concave distributions. Electronic Comm. Probab. 21:1–14.Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12(10):1094–1104.Google Scholar
• Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA (2016) Universality of load balancing schemes on the diffusion scale. J. Appl. Probab. 53(4):1111–1124.Google Scholar
• Ross N (2011) Fundamentals of Stein’s method. Probab. Surveys 8:210–293.Google Scholar
• Stein C (1972) Probability theory: A bound for the error in the normal approximation to the distribution of a sum of dependent random variables, vol. 2, Proc. Sixth Berkeley Sympos. Math. Statist. Probab. (University of California Press, Berkeley), 583–602.Google Scholar
• Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.Google Scholar
• van der Boor M, Borst SC, van Leeuwaarden JSH, Mukherjee D (2021) Scalable load balancing in networked systems: A survey of recent advances. Preprint, submitted November 4, https://arxiv.org/abs/1806.05444.Google Scholar
• Vvedenskaya N, Dobrushin R, Karpelevich F (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems Inform. Transmission 32(1):15–27.Google Scholar
• Weber RR (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15(2):406–413.Google Scholar
• Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probab. 14(1):181–189.Google Scholar
• Ying L (2017) Stein’s method for mean field approximations in light and heavy traffic regimes. Proc. ACM Measurement Anal. Comput. Systems 1(1):1–27.Google Scholar
• Zhao Z, Banerjee S, Mukherjee D (2021) Many-server asymptotics for join-the-shortest queue in the super-Halfin-Whitt scaling window. Preprint submitted May 31, https://arxiv.org/abs/2106.00121.Google Scholar
• Zhou X, Shroff N (2020a) A note on load balancing in many-server heavy-traffic regime. Preprint, submitted April 20, https://arxiv.org/abs/2004.09574v1.Google Scholar
• Zhou X, Shroff N (2020b) A note on Stein’s method for heavy-traffic analysis. Preprint, submitted Mar 13, https://arxiv.org/abs/2003.06454v1.Google Scholar