{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:30:38Z","timestamp":1764783038659,"version":"3.46.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T00:00:00Z","timestamp":1764633600000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CMMI- 2307008,CNS-1955997"],"award-info":[{"award-number":["CMMI- 2307008,CNS-1955997"]}]},{"DOI":"10.13039\/100014037","name":"NDSEG","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100014037","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>\n                    We consider the problem of scheduling to minimize asymptotic tail latency in the M\/G\/\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    queue with light-tailed job size distribution. This problem combines the challenges of scheduling for tail latency and scheduling in multiserver queues, but there is hope. In the simpler setting of the single-server M\/G\/1, the recently proposed\n                    <jats:italic toggle=\"yes\">\u0263-Boost<\/jats:italic>\n                    policy is tail constant optimal, and it has excellent empirical tail latency. And for the simpler objective of mean latency, it is known that the optimal policy in the M\/G\/1, namely SRPT (shortest remaining processing time), is also excellent in the M\/G\/\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    : it is provably optimal in heavy traffic and has state-of-the-art empirical performance in lighter traffic.\n                  <\/jats:p>\n                  <jats:p>\n                    One might therefore hope that\n                    <jats:italic toggle=\"yes\">\u0263<\/jats:italic>\n                    -Boost is similarly effective in the M\/G\/\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    , but our results paint a more complicated picture. In heavy traffic, we prove that\n                    <jats:italic toggle=\"yes\">\u0263<\/jats:italic>\n                    -Boost is indeed tail constant optimal. We also prove an analogous result for scheduling with unknown sizes, where\n                    <jats:italic toggle=\"yes\">\u0263<\/jats:italic>\n                    -Boost is replaced by its unknown-size counterpart. But in lighter traffic, we find empirically that\n                    <jats:italic toggle=\"yes\">\u0263<\/jats:italic>\n                    -Boost can be even worse than FCFS (first-come, first-served). This is a significant shortcoming, as the boundary between ''lighter'' and ''heavy'' traffic occurs at higher load when the number of servers\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    is larger. To overcome this, we design a new variant of\n                    <jats:italic toggle=\"yes\">\u0263<\/jats:italic>\n                    -Boost that outperforms the original by, counterintuitively,\n                    <jats:italic toggle=\"yes\">giving more priority to larger jobs.<\/jats:italic>\n                    The new variant, which we prove is also heavy-traffic optimal, has state-of-the-art empirical tail latency at lighter loads, outperforming even a much more computationally intensive mixed-integer-programming heuristic.\n                  <\/jats:p>","DOI":"10.1145\/3771561","type":"journal-article","created":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T20:07:03Z","timestamp":1764706023000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Tale of Two Traffics: Optimizing Tail Latency in the Light-Tailed M\/G\/k"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3013-8558","authenticated-orcid":false,"given":"George","family":"Yu","sequence":"first","affiliation":[{"name":"School of Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2627-0012","authenticated-orcid":false,"given":"Amit","family":"Harlev","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3557-6946","authenticated-orcid":false,"given":"Reevu","family":"Adakroy","sequence":"additional","affiliation":[{"name":"School of Operations Research and Information Engineering, College of Computing and Information Science, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8547-1068","authenticated-orcid":false,"given":"Ziv","family":"Scully","sequence":"additional","affiliation":[{"name":"School of Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,12,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01158960"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019104402024"},{"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.1287\/moor.21.2.257"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243406"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Nils Charlet and Benny Van Houdt. 2024. Tail Optimality and Performance Analysis of the Nudge-M Scheduling Algorithm. arXiv:2403.06588 [cs math] doi:10.48550\/arXiv.2403.06588","DOI":"10.48550\/arXiv.2403.06588"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCS.2007.365008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.34.9.1121"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.5.1117"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1979.tb01068.x"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470980033"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860300278"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-013-0325-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.4.609.11225"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2019.0042"},{"key":"e_1_2_1_17_1","unstructured":"Isaac Grosof. 2023. Optimal Scheduling in Multiserver Queues. Ph.D. Dissertation. Carnegie Mellon University Pittsburgh PA. https:\/\/isaacg1.github.io\/assets\/isaac-thesis.pdf"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2018.10.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570612"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695411.3695421"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460088"},{"key":"e_1_2_1_22_1","unstructured":"Gurobi Optimization LLC. 2024. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.3.567"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139226424"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3727109"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626570.3626583"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692642"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Prakirt Raj Jhunjhunwala Daniela Hurtado-Lange and Siva Theja Maguluri. 2023. Exponential Tail Bounds on Queues: A Confluence of Non-Asymptotic Heavy Traffic and Large Deviations. arXiv:2306.10187 [math] doi:10.48550\/arXiv.2306.10187","DOI":"10.48550\/arXiv.2306.10187"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005062"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1028903380"},{"volume-title":"Poisson Processes. Number 3 in Oxford Studies in Probability","author":"Kingman John F. C.","key":"e_1_2_1_31_1","unstructured":"John F. C. Kingman. 1993. Poisson Processes. Number 3 in Oxford Studies in Probability. Oxford University Press, Oxford."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212698"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2001.06005"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.018"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991992"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-39105-7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326349408807301"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189231"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/apr.2016.84"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/1427838"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512798.3512812"},{"key":"e_1_2_1_43_1","unstructured":"Ziv Scully. 2022b. 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_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428328"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2020.102150"},{"key":"e_1_2_1_46_1","volume-title":"Probability Theory: An Analytic View (2 ed.)","author":"Stroock Daniel W.","year":"2011","unstructured":"Daniel W. Stroock. 2011. Probability Theory: An Analytic View (2 ed.). Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570610"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1086"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656011"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771561","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:26:01Z","timestamp":1764782761000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3771561"],"URL":"https:\/\/doi.org\/10.1145\/3771561","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-12-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}