{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T20:18:54Z","timestamp":1764793134786,"version":"3.44.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-2307008"],"award-info":[{"award-number":["CMMI-2307008"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"DOD U.S. Department of Defense","doi-asserted-by":"publisher","award":["NDSEG Fellowship"],"award-info":[{"award-number":["NDSEG Fellowship"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,5,27]]},"abstract":"<jats:p>We consider the problem of scheduling to minimize asymptotic tail latency in an M\/G\/1 queue with unknown job sizes. When the job size distribution is heavy-tailed, numerous policies that do not require job size information (e.g. Processor Sharing, Least Attained Service) are known to be strongly tail optimal, meaning that their response time tail has the fastest possible asymptotic decay. In contrast, for light-tailed size distributions, only in the last few years have policies been developed that outperform simple First-Come First-Served (FCFS). The most recent of these is \u03b3-Boost, which achieves strong tail optimality in the light-tailed setting. But thus far, all policies that outperform FCFS in the light-tailed setting, including \u03b3-Boost, require known job sizes. In this paper, we design a new scheduling policy that achieves strong tail optimality in the light-tailed M\/G\/1 with unknown job sizes. Surprisingly, the optimal policy turns out to be a variant of the Gittins policy, but with a novel and unusual feature: it uses a negative discount rate. Our work also applies to systems with partial information about job sizes, covering \u03b3-Boost as an extreme case when job sizes are in fact fully known.<\/jats:p>","DOI":"10.1145\/3727109","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T09:43:35Z","timestamp":1749030215000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Gittins Policy for Optimizing Tail Latency"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2627-0012","authenticated-orcid":false,"given":"Amit","family":"Harlev","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3013-8558","authenticated-orcid":false,"given":"George","family":"Yu","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8547-1068","authenticated-orcid":false,"given":"Ziv","family":"Scully","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326349408807290"},{"key":"e_1_2_1_2_1","volume-title":"SP-PIFO: Approximating Push-in First-out Behaviors Using Strict-Priority Queues. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI","author":"Alcoz Albert Gran","year":"2020","unstructured":"Albert Gran Alcoz, Alexander Dietm\u00fcller, and Laurent Vanbever. 2020. SP-PIFO: Approximating Push-in First-out Behaviors Using Strict-Priority Queues. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2020). USENIX Association, Santa Clara, CA, 59--76. https:\/\/www.usenix.org\/conference\/nsdi20\/presentation\/alcoz"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/b97236"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2007.01.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243406"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212174"},{"key":"e_1_2_1_7_1","unstructured":"Nils Charlet and Benny Van Houdt. 2024. Tail Optimality and Performance Analysis of the Nudge-M Scheduling Algorithm. arxiv: 2403.06588 [cs math] http:\/\/arxiv.org\/abs\/2403.06588"},{"key":"e_1_2_1_8_1","unstructured":"Nicolas Gast Bruno Gaujal and Kimang Khun. 2022. Computing Whittle (and Gittins) Index in Subcubic Time. showeprint[hal]hal-03602458"},{"key":"e_1_2_1_9_1","volume-title":"Weber","author":"Gittins John C.","year":"2011","unstructured":"John C. Gittins, Kevin D. Glazebrook, and Richard R. Weber. 2011. Multi-Armed Bandit Allocation Indices 2 ed.). Wiley, Chichester, UK. QA279. G55 2011"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460088"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139226424"},{"key":"e_1_2_1_12_1","volume-title":"John Edensor Littlewood, and George P\u00f3lya","author":"Hardy Godfrey H.","year":"1952","unstructured":"Godfrey H. Hardy, John Edensor Littlewood, and George P\u00f3lya. 1952. Inequalities 2 ed.). Cambridge Univ. Press, Cambridge."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.4.983"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792545"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005062"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1028903380"},{"key":"e_1_2_1_17_1","volume-title":"Poisson Processes. Number 3 in Oxford Studies in Probability","author":"Kingman John F. C.","year":"1993","unstructured":"John F. C. Kingman. 1993. Poisson Processes. Number 3 in Oxford Studies in Probability. Oxford University Press, Oxford. QA274.42. K56 1993"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.0940"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991992"},{"volume-title":"The Cram\u00e9r--Lundberg model and its variants: A queueing perspective","author":"Mandjes Michel","key":"e_1_2_1_20_1","unstructured":"Michel Mandjes and Onno Boxma. 2023. The Cram\u00e9r--Lundberg model and its variants: A queueing perspective. Springer Nature."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3"},{"volume-title":"A New Toolbox for Scheduling Theory. Ph.,D. Dissertation","author":"Scully Ziv","key":"e_1_2_1_22_1","unstructured":"Ziv Scully. 2022. A New Toolbox for Scheduling Theory. Ph.,D. Dissertation. Carnegie Mellon University, Pittsburgh, PA. https:\/\/ziv.codes\/pdf\/scully-thesis.pdf"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428328"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.23919\/WiOpt52861.2021.9589051"},{"key":"e_1_2_1_25_1","volume-title":"Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs. arxiv","author":"Scully Ziv","year":"1805","unstructured":"Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. 2018a. Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs. arxiv: 1805.06865 [cs, math] https:\/\/arxiv.org\/abs\/1805.06865"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219617.3219632"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/998926986"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570610"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005588"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964800000826"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994469"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1086"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.30.2.223"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3652963.3655084"}],"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\/3727109","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:30:54Z","timestamp":1755898254000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,27]]}},"alternative-id":["10.1145\/3727109"],"URL":"https:\/\/doi.org\/10.1145\/3727109","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"2025-06-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}