{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:44:56Z","timestamp":1761324296992,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T00:00:00Z","timestamp":1591660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["DGE-1745016, DGE-125222, CNS-1518941"],"award-info":[{"award-number":["DGE-1745016, DGE-125222, CNS-1518941"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,6,9]]},"abstract":"<jats:p>We consider the tail behavior of the response time distribution in an M\/G\/1 queue with heavy-tailed job sizes, specifically those with intermediately regularly varying tails. In this setting, the response time tail of many individual policies has been characterized, and it is known that policies such as Shortest Remaining Processing Time (SRPT) and Foreground-Background (FB) have response time tails of the same order as the job size tail, and thus such policies are tail-optimal. Our goal in this work is to move beyond individual policies and characterize the set of policies that are tail-optimal. Toward that end, we use the recently introduced SOAP framework to derive sufficient conditions on the form of prioritization used by a scheduling policy that ensure the policy is tail-optimal. These conditions are general and lead to new results for important policies that have previously resisted analysis, including the Gittins policy, which minimizes mean response time among policies that do not have access to job size information. As a by-product of our analysis, we derive a general upper bound for fractional moments of M\/G\/1 busy periods, which is of independent interest.<\/jats:p>","DOI":"10.1145\/3392148","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T22:10:12Z","timestamp":1591740612000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job Sizes"],"prefix":"10.1145","volume":"4","author":[{"given":"Ziv","family":"Scully","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucas","family":"van Kreveld","sequence":"additional","affiliation":[{"name":"University of Amsterdam, Amsterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Onno","family":"Boxma","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan-Pieter","family":"Dorsman","sequence":"additional","affiliation":[{"name":"University of Amsterdam, Amsterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243409"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-009-9141-x"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-006-7586-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0890"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008732"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"N. Bingham C. Goldie and J. Teugels. 1987. Regular Variation .Cambridge University Press.  N. Bingham C. Goldie and J. Teugels. 1987. Regular Variation .Cambridge University Press.","DOI":"10.1017\/CBO9780511721434"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-5316(03)00071-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-006-7585-9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-011-9229-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243406"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212351"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of ACM Sigmetrics '96","author":"Crovella M.","year":"1996","unstructured":"M. Crovella and A. Bestavros . 1996. Self-similarity in World Wide Web traffic: evidence and possible causes . Proceedings of ACM Sigmetrics '96 ( 1996 ), 160--169. M. Crovella and A. Bestavros. 1996. Self-similarity in World Wide Web traffic: evidence and possible causes. Proceedings of ACM Sigmetrics '96 (1996), 160--169."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"S. Foss D. Korshunov and S. Zachary. 2013. An Introduction to Heavy-tailed and Subexponential Distributions .Springer New York NY.  S. Foss D. Korshunov and S. Zachary. 2013. An Introduction to Heavy-tailed and Subexponential Distributions .Springer New York NY.","DOI":"10.1007\/978-1-4614-7101-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1086957584"},{"key":"e_1_2_1_15_1","first-page":"217","article-title":"The curious history of Fa\u00e0 di Bruno's formula","volume":"109","author":"Johnson W.","year":"2002","unstructured":"W. Johnson . 2002 . The curious history of Fa\u00e0 di Bruno's formula . The American Mathematical Monthly , Vol. 109 , 3 (2002), 217 -- 234 . W. Johnson. 2002. The curious history of Fa\u00e0 di Bruno's formula. The American Mathematical Monthly , Vol. 109, 3 (2002), 217--234.","journal-title":"The American Mathematical Monthly"},{"volume-title":"Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE, 345--352","author":"Kalyanasundaram B.","key":"e_1_2_1_16_1","unstructured":"B. Kalyanasundaram and K. R. Pruhs . 1997. Minimizing flow time nonclairvoyantly . In Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE, 345--352 . B. Kalyanasundaram and K. R. Pruhs. 1997. Minimizing flow time nonclairvoyantly. In Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE, 345--352."},{"volume-title":"Proceedings of the Thirteenth EuroSys Conference . 1--13","author":"Morris N.","key":"e_1_2_1_17_1","unstructured":"N. Morris , C. Stewart , L. Chen , R. Birke , and J. Kelley . 2018. Model-driven computational sprinting . In Proceedings of the Thirteenth EuroSys Conference . 1--13 . N. Morris, C. Stewart, L. Chen, R. Birke, and J. Kelley. 2018. Model-driven computational sprinting. In Proceedings of the Thirteenth EuroSys Conference . 1--13."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.08.012"},{"key":"e_1_2_1_19_1","article-title":"Queues with equally heavy sojourn time and service requirement distributions","volume":"113","author":"Queija R.","year":"2002","unstructured":"R. N\u00fa n ez- Queija . 2002 . Queues with equally heavy sojourn time and service requirement distributions . Annals of Operations Research , Vol. 113 , 1 (01 Jul 2002), 101--117. https:\/\/doi.org\/10.1023\/A:1020905810996 10.1023\/A:1020905810996 R. N\u00fa n ez-Queija. 2002. Queues with equally heavy sojourn time and service requirement distributions. Annals of Operations Research , Vol. 113, 1 (01 Jul 2002), 101--117. https:\/\/doi.org\/10.1023\/A:1020905810996","journal-title":"Annals of Operations Research"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2007.06.028"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0504"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"K. Park and W. Willinger. 2000. Self-similar Network Traffic and Performance Evaluation .Wiley.  K. Park and W. Willinger. 2000. Self-similar Network Traffic and Performance Evaluation .Wiley.","DOI":"10.1002\/047120644X"},{"key":"e_1_2_1_23_1","volume-title":"CMG Proceedings","author":"Peterson D.","year":"1996","unstructured":"D. Peterson . 1996 . Data center I\/O patterns and power laws . CMG Proceedings (1996). D. Peterson. 1996. Data center I\/O patterns and power laws. CMG Proceedings (1996)."},{"volume-title":"Proceedings of the 18th Symposium on High Performance Computer Architecture. IEEE, 1--12","author":"Raghavan A.","key":"e_1_2_1_24_1","unstructured":"A. Raghavan , Y. Luo , A. Chandawalla , M. Papaefthymiou , K. Pipe , T. Wenisch , and M. Martin . 2012. Computational sprinting . In Proceedings of the 18th Symposium on High Performance Computer Architecture. IEEE, 1--12 . A. Raghavan, Y. Luo, A. Chandawalla, M. Papaefthymiou, K. Pipe, T. Wenisch, and M. Martin. 2012. Computational sprinting. In Proceedings of the 18th Symposium on High Performance Computer Architecture. IEEE, 1--12."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1396360104"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.670"},{"key":"e_1_2_1_27_1","volume-title":"SOAP Bubbles: Robust Scheduling Under Adversarial Noise. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) . 144--154","author":"Scully Z.","year":"2018","unstructured":"Z. Scully and M. Harchol-Balter . 2018 . SOAP Bubbles: Robust Scheduling Under Adversarial Noise. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) . 144--154 . https:\/\/doi.org\/10.1109\/ALLERTON. 2018 .8635963 10.1109\/ALLERTON.2018.8635963 Z. Scully and M. Harchol-Balter. 2018. SOAP Bubbles: Robust Scheduling Under Adversarial Noise. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) . 144--154. https:\/\/doi.org\/10.1109\/ALLERTON.2018.8635963"},{"key":"e_1_2_1_28_1","first-page":"30 pages. https","volume-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","volume":"2","author":"Scully Z.","year":"2018","unstructured":"Z. Scully , M. Harchol-Balter , and A. Scheller-Wolf . 2018. SOAP: one clean analysis of all age-based scheduling policies . Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 2 , 1, Article 16 ( April 2018 ), bibinfonumpages 30 pages. https:\/\/doi.org\/10 .1145\/3179419 10.1145\/3179419 Z. Scully, M. Harchol-Balter, and A. Scheller-Wolf. 2018. SOAP: one clean analysis of all age-based scheduling policies. Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 2, 1, Article 16 (April 2018), bibinfonumpages30 pages. https:\/\/doi.org\/10.1145\/3179419"},{"key":"e_1_2_1_29_1","first-page":"29 pages. https","volume-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","volume":"4","author":"Scully Z.","year":"2020","unstructured":"Z. Scully , M. Harchol-Balter , and A. Scheller-Wolf . 2020. Simple Near-Optimal Scheduling for the M\/G\/1 . Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 4 , 1, Article 11 ( March 2020 ), bibinfonumpages 29 pages. https:\/\/doi.org\/10 .1145\/3379477 10.1145\/3379477 Z. Scully, M. Harchol-Balter, and A. Scheller-Wolf. 2020. Simple Near-Optimal Scheduling for the M\/G\/1. Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 4, 1, Article 11 (March 2020), bibinfonumpages29 pages. https:\/\/doi.org\/10.1145\/3379477"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/998926986"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1086"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019142010994"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392148","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3392148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:49Z","timestamp":1750199929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,9]]}},"alternative-id":["10.1145\/3392148"],"URL":"https:\/\/doi.org\/10.1145\/3392148","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2020,6,9]]},"assertion":[{"value":"2020-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}