When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1?

References

• Aalto S, Ayesta U, Righter R (2009) On the Gittins index in the M/G/1 queue. Queueing Systems 63(1–4):437–458.Crossref, Google Scholar
• Aalto S, Ayesta U, Righter R (2011) Properties of the Gittins index with application to optimal scheduling. Probab. Engrg. Inform. Sci. 25(3):269–288.Crossref, Google Scholar
• Abate J, Whitt W (1997) Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25(1):173–233.Crossref, Google Scholar
• Bingham NH, Goldie CM, Teugels JL (1987) Regular Variation, Encyclopedia of Mathematics and Its Applications, vol. 27 (Cambridge University Press, Cambridge, UK).Google Scholar
• Borst SC, Boxma OJ, Núñez-Queija R, Zwart B (2003) The impact of the service discipline on delay asymptotics. Performance Eval. 54(2):175–206.Crossref, Google Scholar
• Boxma OJ, Zwart B (2007) Tails in scheduling. ACM SIGMETRICS Performance Eval. Rev. 34(4):13–20.Crossref, Google Scholar
• Cline DBH (1994) Intermediate regular and Π variation. Proc. London Math. Soc. s3-68(3):594–616.Crossref, Google Scholar
• Cox DR, Smith WL (1961) Queues (Methuen, London).Google Scholar
• Crovella ME, Bestavros A (1997) Self-similarity in World Wide Web traffic: Evidence and possible causes. IEEE/ACM Trans. Networking 5(6):835–846.Crossref, Google Scholar
• Gittins JC (1989) Multi-Armed Bandit Allocation Indices, 1st ed., Wiley-Interscience Series in Systems and Optimization (Wiley, Chichester, UK).Google Scholar
• Gittins JC, Glazebrook KD, Weber RR (2011) Multi-Armed Bandit Allocation Indices, 2nd ed. (Wiley, Chichester, UK).Crossref, Google Scholar
• Grosof I, Yang K, Scully Z, Harchol-Balter M (2021) Nudge: Stochastically improving upon FCFS. Proc. ACM Measurement Anal. Comput. Systems 5(2):21.Google Scholar
• Harchol-Balter M (2013) Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Harchol-Balter M, Downey AB (1997) Exploiting process lifetime distributions for dynamic load balancing. ACM Trans. Comput. Systems 15(3):253–285.Crossref, Google Scholar
• Kendall DG (1953) Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. Ann. Math. Statist. 24(3):338–354.Crossref, Google Scholar
• Kleinrock L (1976) Computer Applications, Queueing Systems, vol. 2 (Wiley, New York).Google Scholar
• Mandjes M, Nuyens M (2005) Sojourn times in the M/G/1 FB queue with light-tailed service times. Probab. Engrg. Inform. Sci. 19(3):351–361.Crossref, Google Scholar
• Mimica A (2016) Exponential decay of measures and Tauberian theorems. J. Math. Anal. Appl. 440(1):266–285.Crossref, Google Scholar
• Nair J, Wierman A, Zwart B (2010) Tail-robust scheduling via limited processor sharing. Performance Eval. 67(11):978–995.Crossref, Google Scholar
• Nakagawa K (2005) Tail probability of random variable and Laplace transform. Applicable Anal. 84(5):499–522.Crossref, Google Scholar
• Nakagawa K (2007) Application of Tauberian theorem to the exponential decay of the tail probability of a random variable. IEEE Trans. Inform. Theory 53(9):3239–3249.Crossref, Google Scholar
• Núñez-Queija R (2002) Queues with equally heavy sojourn time and service requirement distributions. Ann. Oper. Res. 113(1/4):101–117.Crossref, Google Scholar
• Peterson DL (1996) Data center I/O patterns and power laws. 22nd International Computer Measurement Group Conference (Computer Measurement Group, San Diego), 1034–1045.Google Scholar
• Schrage LE (1968) A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(3):687–690.Link, Google Scholar
• Scully Z (2022) A new toolbox for scheduling theory. PhD thesis, Carnegie Mellon University, Pittsburgh.Google Scholar
• Scully Z, Harchol-Balter M (2018) SOAP bubbles: Robust scheduling under adversarial noise. 56th Annu. Allerton Conf. Commun. Control Comput. (IEEE, Monticello, IL), 144–154.Google Scholar
• Scully Z, Harchol-Balter M (2021) The Gittins policy in the M/G/1 queue. 19th Internat. Sympos. Modeling Optim. Mobile Ad Hoc Wireless Networks WiOpt 2021 (IFIP, Philadelphia), 248–255.Google Scholar
• Scully Z, Grosof I, Harchol-Balter M (2020a) The Gittins policy is nearly optimal in the M/G/k under extremely general conditions. Proc. ACM Measurement Anal. Comput. Systems 4(3):43.Google Scholar
• Scully Z, Grosof I, Harchol-Balter M (2021) Optimal multiserver scheduling with unknown job sizes in heavy traffic. Performance Eval. 145:102150.Crossref, Google Scholar
• Scully Z, Grosof I, Mitzenmacher M (2022) Uniform bounds for scheduling with job size estimates. 13th Innovations Theor. Comput. Sci. Conf. ITCS 2022, Leibniz International Proceedings in Informatics (LIPIcs) (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Berkeley, CA), 114:1–114:30.Google Scholar
• Scully Z, Harchol-Balter M, Scheller-Wolf A (2018) One clean analysis of all age-based scheduling policies. Proc. ACM Measurement Anal. Comput. Systems 2(1):1–30.Google Scholar
• Scully Z, Harchol-Balter M, Scheller-Wolf A (2020b) Simple near-optimal scheduling for the M/G/1. Proc. ACM Measurement Anal. Comput. Systems 4(1):11.Google Scholar
• Scully Z, van Kreveld L, Boxma O, Dorsman J-P, Wierman A (2020c) Characterizing policies with optimal response time tails under heavy-tailed job sizes. Proc. ACM Measurement Anal. Comput. Systems 4(2):30.Google Scholar
• Stolyar AL, Ramanan K (2001) Largest weighted delay first scheduling: Large deviations and optimality. Ann. Appl. Probab. 11(1):1–48.Crossref, Google Scholar
• Wierman A, Zwart B (2012) Is tail-optimal scheduling possible? Oper. Res. 60(5):1249–1257.Link, Google Scholar