Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints

References

• Adan I, Weiss G (2014) A skill based parallel service system under FCFS-ALIS—steady state, overloads, and abandonments. Stochastic Systems 4(1):250–299.Link, Google Scholar
• Adan I, Kleiner I, Righter R, Weiss G (2018) FCFS parallel service systems and matching models. Performance Evaluation 127-128:253–272.Crossref, Google Scholar
• Afèche P, Caldentey R, Gupta V (2021) On the optimal design of a bipartite matching queueing system. Oper. Res. 70(1):363–401.Link, Google Scholar
• Ananthanarayanan G, Ghodsi A, Shenker S, Stoica I (2013) Effective straggler mitigation: Attack of the clones. Proc. 10th USENIX Conf. Networked Systems Design Implementation (USENIX, Lombard, IL), 185–198.Google Scholar
• Anton E, Ayesta U, Jonckheere M, Verloop IM (2021) On the stability of redundancy models. Oper. Res. 69(5):1540–1565.Link, Google Scholar
• Atar R, Keslassy I, Mendelson G (2019a) Replicate to the shortest queues. Queueing Systems 92(1–2):1–23.Crossref, Google Scholar
• Atar R, Keslassy I, Mendelson G (2019b) Subdiffusive load balancing in time-varying queueing systems. Oper. Res. 67(6):1678–1698.Link, Google Scholar
• Ayesta U, Bodas T, Verloop IM (2018) On a unifying product form framework for redundancy models. Performance Evaluation 127–128:93–119.Crossref, Google Scholar
• Ayesta U, Bodas T, Dorsman JL, Verloop IM (2021) A token-based central queue with order-independent service rates. Oper. Res. 70(1):545–561.Link, Google Scholar
• Banerjee S, Kanoria Y, Qian P (2020) Dynamic assignment control of a closed queueing network under complete resource pooling. Preprint, submitted June 25, https://arxiv.org/abs/1803.04959.Google Scholar
• Bell SL, Williams RJ (2001) Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy. Ann. Appl. Probab. 11(3):608–649.Crossref, Google Scholar
• Bonald T, Comte C (2017) Balanced fair resource sharing in computer clusters. Performance Evaluation 116:70–83.Crossref, Google Scholar
• Bonald T, Comte C, Mathieu F (2017) Performance of balanced fairness in resource pools: A recursive approach. Proc. ACM Measurement Anal. Comput. Systems 1(2):1–25.Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30(1-2):89–148.Crossref, Google Scholar
• Bramson M (2011) Stability of join the shortest queue networks. Ann. Appl. Probab. 21(4):1568–1625.Crossref, Google Scholar
• Budhiraja A, Mukherjee D, Wu R (2019) Supermarket model on graphs. Ann. Appl. Probab. 29(3):1740–1777.Crossref, Google Scholar
• Chen H, Ye HQ (2012) Asymptotic optimality of balanced routing. Oper. Res. 60(1):163–179.Link, Google Scholar
• Cruise J, Jonckheere M, Shneer S (2020) Stability of JSQ in queues with general server-job class compatibilities. Queueing Systems 95(3):271–279.Crossref, Google Scholar
• Dai JG, Lin W (2008) Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probab. 18(6):2239–2299.Crossref, Google Scholar
• Eschenfeldt P, Gamarnik D (2017) Supermarket queueing system in the heavy traffic regime. Short queue dynamics. Preprint, submitted January 17, https://arxiv.org/abs/1610.03522.Google Scholar
• Feller W (1971) An Introduction to Probability Theory and Its Applications, 2nd ed., Wiley Series in Probability and Statistics, vol. 2 (Wiley, Hoboken, NJ).Google Scholar
• Fleming PJ, Simon B (1999) Heavy-traffic approximations for a system of infinite servers with load balancing. Probab. Engrg. Inform. Sci. 13(3):251–273.Crossref, Google Scholar
• Foss SG, Chernova NI (1998) On the stability of a partially accessible multi-station queue with state-dependent routing. Queueing Systems 29(1):55–73.Crossref, Google Scholar
• Gardner K, Righter R (2020) Product forms for FCFS queueing models with arbitrary server-job compatibilities: An overview. Queueing Systems 96(1–2):3–51.Crossref, Google Scholar
• Gardner K, Harchol-Balter M, Hyytiä E, Righter R (2017a) Scheduling for efficiency and fairness in systems with redundancy. Performance Evaluation 116:1–25.Crossref, Google Scholar
• Gardner K, Harchol-Balter M, Scheller-Wolf A, Velednitsky M, Zbarsky S (2017b) Redundancy-d: The power of d choices for redundancy. Oper. Res. 65(4):1078–1094.Link, Google Scholar
• Gardner K, Zbarsky S, Doroudi S, Harchol-Balter M, Hyytiä E, Scheller-Wolf A (2016) Queueing with redundant requests: Exact analysis. Queueing Systems 83(3-4):227–259.Crossref, Google Scholar
• Gast N (2015) The power of two choices on graphs: The pair-approximation is accurate? ACM SIGMETRICS Performance Evaluation Rev. 43(2):69–71.Crossref, Google Scholar
• Graves SC, Tomlin BT (2003) Process flexibility in supply chains. Management Sci. 49(7):907–919.Link, Google Scholar
• Harrison JM (1998) Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Ann. Appl. Probab. 8(3):822–848.Crossref, Google Scholar
• Harrison JM, López MJ (1999) Heavy traffic resource pooling in parallel server systems. Queueing Systems 33(4):339–368.Crossref, Google Scholar
• He YT, Down DG (2008) Limited choice and locality considerations for load balancing. Performance Evaluation 65(9):670–687.Crossref, Google Scholar
• Hellemans T, Van Houdt B (2018) On the power-of-d-choices with least loaded server selection. Proc. ACM Measurement Anal. Comput. Systems 2(2):1–22.Google Scholar
• Hellemans T, Van Houdt B (2021) Mean waiting time in large-scale and critically loaded power of d load balancing systems. Proc. ACM Measurement Anal. Comput. Systems 5(2):1–34.Google Scholar
• Hellemans T, Bodas T, Van Houdt B (2019) Performance analysis of workload dependent load balancing policies. Proc. ACM Measurement Anal. Comput. Systems 3(2):1–35.Google Scholar
• Hurtado-Lange D, Maguluri ST (2020) Transform methods for heavy-traffic analysis. Stochastic Systems 10(4):275–309.Link, Google Scholar
• Hurtado-Lange D, Maguluri ST (2021) Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems. Oper. Res. Lett. 49(4):616–622.Crossref, Google Scholar
• Jordan WC, Graves SC (1995) Principles on the benefits of manufacturing process flexibility. Management Sci. 41(4):577–594.Link, Google Scholar
• Joshi G (2018) Synergy via redundancy: Boosting service capacity with adaptive replication. ACM SIGMETRICS Performance Evaluation Rev. 45(3):21–28.Crossref, Google Scholar
• Joshi G, Soljanin E, Wornell G (2017) Efficient redundancy techniques for latency reduction in cloud systems. ACM Trans. Modelling Performance Evaluation Comput. Systems 2(2):12.Google Scholar
• Keilson J, Servi LD (1988) A distributional form of Little’s law. Oper. Res. Lett. 7(5):223–227.Crossref, Google Scholar
• Kelly FP, Laws CN (1993) Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems 13(1–3):47–86.Crossref, Google Scholar
• Krzesinski AE (2011) Order independent queues. Boucherie R, van Dijk N, eds. Queueing Networks, International Series in Operations Research and Management Science, vol. 154 (Springer, Boston), 85–120.Crossref, Google Scholar
• Laws CN (1992) Resource pooling in queueing networks with dynamic routing. Adv. Appl. Probab. 24(3):699–726.Crossref, Google Scholar
• Lee K, Pedarsani R, Ramchandran K (2017) On scheduling redundant requests with cancellation overheads. IEEE/ACM Trans. Networking 25(2):1279–1290.Crossref, Google Scholar
• Maguluri ST, Srikant R (2015) Heavy-traffic behavior of the Maxweight algorithm in a switch with uniform traffic. ACM SIGMETRICS Performance Evaluation Rev. 43(2):72–74.Crossref, Google Scholar
• Mandelbaum A, Stolyar AL (2004) Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule. Oper. Res. 52(6):836–855.Link, Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12(10):1094–1104.Crossref, Google Scholar
• Mukherjee D, Borst SC, van Leeuwaarden JSH (2018) Asymptotically optimal load balancing topologies. Proc. ACM Measurement Anal. Comput. Systems 2(1):1–29.Google Scholar
• Rutten D, Mukherjee D (2022) Load balancing under strict compatibility constraints. Math. Oper. Res., ePub ahead of print April 20, https://doi.org/10.1287/moor.2022.1258.Link, Google Scholar
• Shah D, Wischik D (2012) Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse. Ann. Appl. Probab. 22(1):70–127.Crossref, Google Scholar
• Shah NB, Lee K, Ramchandran K (2016) When do redundant requests reduce latency? IEEE Trans. Comm. 64(2):715–722.Crossref, Google Scholar
• Sharifnassab A, Tsitsiklis JN, Golestani SJ (2020) Fluctuation bounds for the Max-weight policy with applications to state space collapse. Stochastic Systems 10(3):223–250.Link, Google Scholar
• Shi C, Wei Y, Zhong Y (2019) Process flexibility for multiperiod production systems. Oper. Res. 67(5):1300–1320.Link, Google Scholar
• Simchi-Levi D, Wei Y (2012) Understanding the performance of the long chain and sparse designs in process flexibility. Oper. Res. 60(5):1125–1141.Link, Google Scholar
• Sloothaak F, Cruise J, Shneer S, Vlasiou M, Zwart B (2021) Complete resource pooling of a load-balancing policy for a network of battery swapping stations. Queueing Systems 99(1–2):65–120.Crossref, Google Scholar
• Stolyar AL (2004) MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1):1–53.Crossref, Google Scholar
• Stolyar AL (2005) Optimal routing in output-queued flexible server systems. Probab. Engrg. Inform. Sci. 19(2):141–189.Crossref, 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
• Tsitsiklis JN, Xu K (2013) Queueing system topologies with limited flexibility. ACM SIGMETRICS Performance Evaluation Rev. 41(1):167–178.Google Scholar
• Tsitsiklis JN, Xu K (2017) Flexible queueing architectures. Oper. Res. 5(65):1398–1413.Link, Google Scholar
• Turner SRE (1998) The effect of increasing routing choice on resource pooling. Probab. Engrg. Inform. Sci. 12(1):109–124.Crossref, Google Scholar
• Varma SM, Maguluri ST (2021) Transportation polytope and its applications in parallel server systems. Preprint, submitted August 11, https://arxiv.org/abs/2108.13167.Google Scholar
• Visschers J, Adan I, Weiss G (2012) A product form solution to a system with multi-type jobs and multi-type servers. Queueing Systems 70(3):269–298.Crossref, 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
• Weng W, Zhou X, Srikant R (2020) Optimal load balancing with locality constraints. Proc. ACM Measurement Anal. Comput. Systems 4(3):1–37.Google Scholar
• Zheng L, Chandratre S, Ali A, Szabo A, Durham L, Joyce LD, Joyce DL (2022) How does multiple listing affect lung transplantation? A retrospective analysis. Seminars Thoracic Cardiovascular Surgery 34(1):326–335.Crossref, Google Scholar