Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System

References

• Aghajani R, Ramanan K (2017) The hydrodynamic limit of a randomized load balancing network. Working paper, University of California, San Diego, San Diego.Google Scholar
• Andrew LLH, Lin M, Wierman A (2010) Optimality, fairness, and robustness in speed scaling designs. ACM SIGMETRICS Performance Evaluation Rev. 38(1):37–48.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
• Bramson M, Lu Y, Prabhakar B (2013) Decay of tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Probab. 23(5):1841–1878.Google Scholar
• Dai JG (1995) On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5(1):49–77.Google Scholar
• Eschenfeldt P, Gamarnik D (2016) Supermarket queueing system in the heavy traffic regime. Short queue dynamics. Working paper, Massachusetts General Hospital, Boston.Google Scholar
• Foss SG, Stolyar AL (2017) Large-scale join-idle-queue system with general service times. J. Appl. Probab. 54(4):995–1007.Google Scholar
• Gandhi A, Doroudi S, Harchol-Balter M, Scheller-Wolf A (2014) Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward. Queueing Systems 77(2):177–209.Google Scholar
• Liggett TM (1985) Interacting Particle Systems (Springer, New York).Google Scholar
• Lin M, Liu Z, Wierman A, Andrew LLH (2012) Online algorithms for geographical load balancing. Internat. Green Comput. Conf. (IEEE, Washington, DC), 1–10.Google Scholar
• Lin M, Wierman A, Andrew LLH, Thereska E (2013) Dynamic right-sizing for power-proportional data centers. IEEE/ACM Trans. Networking 21(5):1378–1391.Google Scholar
• Liu Z, Lin M, Wierman A, Low SH, Andrew LLH (2011a) Geographical load balancing with renewables. ACM SIGMETRICS Performance Evaluation Rev. 39(3):62–66.Google Scholar
• Liu Z, Lin M, Wierman A, Low SH, Andrew LLH (2011b) Greening geographical load balancing. Proc. SIGMETRICS ’11 (ACM, New York), 233–244.Google Scholar
• Liu Z, Chen Y, Bash C, Wierman A, Gmach D, Wang Z, Marwah M, Hyser C (2012) Renewable and cooling aware workload management for sustainable data centers. ACM SIGMETRICS Performance Evaluation Rev. 40(1):175–186.Google Scholar
• Lu Y, Xie Q, Kliot G, Geller A, Larus JR, Greenberg A (2011) Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation 68(11):1056–1071.Google Scholar
• Meyn SP, Tweedie RL (1993) Markov Chains and Stochastic Stability (Springer, London).Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distribution 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
• Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA (2018) Universality of power-of-d load balancing in many-server systems. Stochastic Systems 8(4):265–292.Google Scholar
• Mukherjee D, Dhara S, Borst SC, Van Leeuwaarden JSH (2017) Optimal service elasticity in large-scale distributed systems. Proc. ACM Measurement Anal. Comput. Systems 1(1):3–3.Google Scholar
• Nguyen LM, Stolyar AL (2016) A service system with randomly behaving on-demand Aagents. ACM SIGMETRICS Performance Evaluation Rev. 44(1):365–366.Google Scholar
• Pang G, Stolyar AL (2016) A service system with on-demand agent invitations. Queueing Systems 82(3–4):259–283.Google Scholar
• Pender J, Phung-Duc T (2016) A law of large numbers for M/M/c/delayoff-setup queues with nonstationary arrivals. Wittevrongel S, Phung-Duc T, eds. Proc. ASMTA ’16, Lecture Notes in Computer Science, vol. 9845 (Springer, Cham, Switzerland), 253–268.Google Scholar
• Rybko AN, Stolyar AL (1992) On the ergodicity of stochastic processes describing the operation of open queueing networks. Problems Inform.Transmission 28(3):199–200.Google Scholar
• Shneer S, Stolyar A (2018) Stability conditions for a discrete-time decentralised medium access algorithm. Ann. Appl. Probab. 28(6):3600–3628.Google Scholar
• Stolyar AL (1995) On the stability of multiclass queueing networks: A relaxed sufficient condition via limiting fluid processes. Markov Processes Related Fields 1(4):491–512.Google Scholar
• Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.Google Scholar
• Stolyar AL (2017) Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers. Queueing Systems 85(1):31–65.Google Scholar
• Urgaonkar R, Kozat UC, Igarashi K, Neely MJ (2010) Dynamic resource allocation and power management in virtualized data centers. Proc. IEEE Network Oper. Management Sympos. (NOMS) (IEEE, Washington, DC), 479–486.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, Ney de Souza P, Viana M, eds. Proc. Internat. Congress Mathematicians (World Scientific, Singapore), 3881–3912.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
• Wierman A, Andrew LLH, Tang A (2012) Power-aware speed scaling in processor sharing systems: optimality and robustness. Performance Evaluation 69(12):601–622.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):Article 12.Google Scholar