Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems

References

• Aghajani R, Ramanan K (2017) The hydrodynamic limit of a randomized load balancing network. Preprint arXiv:1707.02005.Google Scholar
• Badonnel R, Burgess M (2008) Dynamic pull-based load balancing for autonomic servers. Brunner N, Becker Westphall C, Zambenedetti Granville L, eds. Proc. Network Oper. Management Sympos. (NOMS), (IEEE, Piscataway, NJ), 751–754.Google Scholar
• Bertsimas D, Gamarnik D, Tsitsiklis JN (2002) Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probab. 11(4):1384–1428.Google Scholar
• Billingsley P (1999) Convergence of Probability Measures, Second ed. (John Wiley & Sons, New York).Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems: Theory Appl. 30(1–2):89–148.Google Scholar
• Bramson M, Lu Y, Prabhakar B (2013) Decay tails at equilibrium for FIFO join the shortest queue networks. Ann. Appl. Probab. 23(5):1841–1878.Google Scholar
• Filippov AF (1988) Differential Equations with Discontinuous Righthand Sides (Springer, Dordrecht, Netherlands).Google Scholar
• Foss S, Stolyar AL (2017) Large-scale join-idle-queue system with general service times. Preprint arXiv:1605.05968.Google Scholar
• Foster FG (1953) On the stochastic matrices associated with certain queueing processes. Ann. Math. Statist. 24(3):355–360.Google Scholar
• Gamarnik D, Tsitsiklis JN, Zubeldia M (2016) Delay, memory, and messaging tradeoffs in distributed service systems. Gamarnik D, Tsitsiklis JN, Zubeldia M, eds. Proc. ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Sci. (ACM, New York), 1–12.Google Scholar
• Hajek B (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3):502–525.Google Scholar
• Hunt PJ, Kurtz TG (1994) Large loss networks. Stochastic Processes and Their Appl. 53(2):363–378.Google Scholar
• Kirszbraun MD (1934) Über die zusammenziehende und Lipschitzsche Transformationen. Fund. Math 22(1):77–108.Google Scholar
• Kurtz TG (1981) Approximation of Population Processes (SIAM, Philadelphia).Google Scholar
• Lobanov SG, Smolyanov OG (1994) Ordinary differential equations in locally convex spaces. Uspekhi Mat. Nauk 49(3):93–168.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
• Mitzenmacher MD (1996) The power of two choices in randomized load balancing. Ph.D. thesis, University of California, Berkeley.Google Scholar
• Mitzenmacher M (2016) Analyzing distributed join-idle-queue: A fluid limit approach. Proc. 54th Annual Allerton Conf. Commun., Control, Comput. (IEEE, Piscataway, NJ), 312–318.Google Scholar
• Mitzenmacher M, Prabhakar B, Shah D (2002) Load balancing with memory. Proc. 43rd Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 799–808.Google Scholar
• Mukherjee D, Borst S, van Leeuwaarden J, Whiting P (2016) Universality of power-of-d load balancing schemes. ACM SIGMETRICS Performance Evaluation Rev. 44(2):36–38.Google Scholar
• Rudin W (1976) Principles of Mathematical Analysis, 3rd ed. (McGraw-Hill, New York).Google Scholar
• Shwartz A, Weiss A (1995) Large Deviations for Performance Analysis: Queues, Communications, and Computing (Chapman & Hall, London).Google Scholar
• Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems: Theory Appl. 80(4):341–361.Google Scholar
• Stolyar AL (2017) Pull-based load distribution among heterogeneous parallel servers: The case of multiple routers. Queueing Systems: Theory Appl. 85(1–2):31–65.Google Scholar
• Tsitsiklis JN, Xu K (2012) On the power of (even a little) resource pooling. Stochastic Systems 2(1):1–66.Link, Google Scholar
• Van Der Boor M, Borst S, van Leeuwaarden J (2017) Load balancing in large-scale systems with multiple dispatchers. Proc. IEEE Conf. Comput. Commun. (INFOCOM) (IEEE, Piscataway, NJ).Google Scholar
• Vvedenskaya ND, Dobrushin RL, Karpelevich FI (1996) Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems Inform. Transmission 32(1):15–27.Google Scholar
• Xu K, Yun S-Y (2017) Reinforcement with fading memories. Preprint.Google Scholar
• Ying L, Srikant R, Kang X (2015) The power of slightly more than one sample in randomized load balancing. Proc. IEEE Conf. Comput. Commun. (INFOCOM) (IEEE, Piscataway, NJ), 1131–1139.Google Scholar