Universality of Power-of-$d$ Load Balancing in Many-Server Systems

References

• Banerjee S, Mukherjee D (2018) Join-the-shortest queue diffusion limit in Halfin-Whitt regime: Tail asymptotics and scaling of extrema. Ann. Appl. Probab. Forthcoming. arXiv preprint available at http://arxiv.org/abs/1803.03306.Google Scholar
• Bramson M, Lu Y, Prabhakar B (2012) Asymptotic independence of queues under randomized load balancing. Queueing Systems 71(3):247–292.Google Scholar
• Braverman A (2018) Steady-state analysis of the join the shortest queue model in the Halfin-Whitt regime. Working paper, Northwestern University, Chicago. https://arxiv.org/pdf/1801.05121.pdf.Google Scholar
• Brightwell G, Fairthorne M, Luczak MJ (2018) The supermarket model with bounded queue lengths in equilibrium. J. Statist. Phys. 173(3‐4):1149–1194.Google Scholar
• Ephremides A, Varaiya P, Walrand J (1980) A simple dynamic routing problem. IEEE Trans. Automatic Control 25(4):690–693.Google Scholar
• Eschenfeldt P, Gamarnik D (2016) Supermarket queueing system in the heavy traffic regime. Short queue dynamics. Working paper, Harvard Medical School, Boston. http://arxiv.org/abs/1610.03522.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
• Ethier SN, Kurtz TG (2009) Markov Processes: Characterization and Convergence (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Gamarnik D, Tsitsiklis J, Zubeldia M (2016) Delay, memory and messaging tradeoffs in distributed service systems. Proc. SIGMETRICS ’16 (ACM, New York), 1–12.Google Scholar
• Graham C (2005) Functional central limit theorems for a large network in which customers join the shortest of several queues. Probab. Theory Related Fields 131(1):97–120.Google Scholar
• Gupta V, Harchol-Balter M, Sigman K, Whitt W (2007) Analysis of join-the-shortest-queue routing for web server farms. Performance Evaluation 64(9–12):1062–1081.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
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Google Scholar
• Hunt P, Kurtz T (1994) Large loss networks. Stochastic Processes Their Appl. 53(2):363–378.Google Scholar
• Jonckheere M (2006) Insensitive versus efficient dynamic load balancing in networks without blocking. Queueing Systems 54(3):193–202.Google Scholar
• Liptser R, Shiryaev A (1989) Theory of Martingales (Springer, New York).Google Scholar
• Luczak MJ, McDiarmid C (2006) On the maximum queue length in the supermarket model. Ann. Probab. 34(2):493–527.Google Scholar
• Luczak MJ, Norris J (2005) Strong approximation for the supermarket model. Ann. Appl. Probab. 15(3):2038–2061.Google Scholar
• Luh K, Pippenger N (2014) Large-deviation bounds for sampling without replacement. Amer. Math. Monthly 121(5):449–454.Google Scholar
• Mitzenmacher M (1996) The power of two choices in randomized load balancing. PhD thesis, University of California, Berkeley.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 (2016a) Asymptotic optimality of power-of-d load balancing in large-scale systems. Working paper, Brown University, Providence, RI. https://arxiv.org/abs/1612.00722.Google Scholar
• Mukherjee D, Borst SC, Van Leeuwaarden JSH, Whiting PA (2016b) Universality of load balancing schemes on the diffusion scale. J. Appl. Probab. 53(4):1111–1124.Google Scholar
• Pang G, Talreja R, Whitt W (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surveys 4:193–267.Google Scholar
• Sparaggis PD, Towsley D, Cassandras CG (1994) Sample path criteria for weak majorization. Adv. Appl. Probab. 26(1):155–171.Google Scholar
• Towsley D (1995) Application of majorization to control problems in queueing systems. Chrétienne P, Coffman EG, Lenstra JK, Liu Z, eds. Scheduling Theory and Its Applications (John Wiley & Sons, Hoboken, NJ), 295–312.Google Scholar
• Towsley D, Sparaggis P, Cassandras C (1992) Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Trans. Automatic Control 37(9):1446–1451.Google Scholar
• Van der Boor M, Borst SC, Van Leeuwaarden JSH, Mukherjee D (2018) Scalable load balancing in networked systems: Universality properties and stochastic coupling methods. Sirakov B, de Souza PN, Viana M, eds. Proc. ICM ’18, Rio de Janeiro, Brazil (World Scientific).Google Scholar
• Van Leeuwaarden JSH, Knessl C (2011) Transient behavior of the Halfin–Whitt diffusion. Stochastic Processes Their Appl. 121(7):1524–1545.Google Scholar
• Van Leeuwaarden JSH, Knessl C (2012) Spectral gap of the Erlang A model in the Halfin-Whitt regime. Stochastic Systems 2(1):149–207.Link, Google Scholar
• Vvedenskaya ND, Dobrushin RL, Karpelevich FI (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii 32(1):20–34.Google Scholar
• Weber RR (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15(2):406–413.Google Scholar
• Whitt W (1986) Deciding which queue to join: Some counterexamples. Oper. Res. 34(1):55–62.Link, Google Scholar
• Whitt W (2002) Stochastic-Process Limits. Springer Series in Operations Research and Financial Engineering (Springer-Verlag, New York).Google Scholar
• Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probab. 14(1):181–189.Google Scholar
• Ying L, Srikant R, Kang X (2015) The power of slightly more than one sample in randomized load balancing. Proc. 2015 IEEE Conf. Comput. Comm., (INFOCOM) (Institute of Electrical and Electronics Engineers Inc., Piscataway, NJ), 1131–1139.Google Scholar