{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T06:58:55Z","timestamp":1771570735712,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T00:00:00Z","timestamp":1513641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003816","name":"Huawei Technologies","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003816","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1446582,CNS-1719371,1717060"],"award-info":[{"award-number":["CNS-1446582,CNS-1719371,1717060"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2417"],"award-info":[{"award-number":["N00014-17-1-2417"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-14-1-0368"],"award-info":[{"award-number":["W911NF-14-1-0368"]}],"id":[{"id":"10.13039\/100000183","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":[[2017,12,19]]},"abstract":"<jats:p>\n            In this paper, we establish a unified analytical framework for designing load balancing algorithms that can simultaneously achieve low latency, low complexity, and low communication overhead. We first propose a general class\n            <jats:italic>\\Pi<\/jats:italic>\n            of load balancing policies and prove that they are throughput optimal and heavy-traffic delay optimal. This class\n            <jats:italic>\\Pi<\/jats:italic>\n            includes popular policies such as join-shortest-queue (JSQ) and power-of-\n            <jats:italic>d<\/jats:italic>\n            as special cases, but not the recently proposed join-idle-queue (JIQ) policy. In fact, we show that JIQ is not heavy-traffic delay optimal even for homogeneous servers. By exploiting the flexibility offered by the class\n            <jats:italic>\\Pi<\/jats:italic>\n            , we design a new load balancing policy called join-below-threshold (JBT-d), in which the arrival jobs are preferably assigned to queues that are no greater than a threshold, and the threshold is updated infrequently. JBT-d has several benefits: (i) JBT-d belongs to the class\n            <jats:italic>\\Pi<\/jats:italic>\n            and hence is throughput optimal and heavy-traffic delay optimal. (ii) JBT-d has zero dispatching delay, like JIQ and other pull-based policies, and low message overhead due to infrequent threshold update. (iii) Extensive simulations show that JBT-d has excellent delay performance, comparable to the JSQ policy in various system settings.\n          <\/jats:p>","DOI":"10.1145\/3154498","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Designing Low-Complexity Heavy-Traffic Delay-Optimal Load Balancing Schemes"],"prefix":"10.1145","volume":"1","author":[{"given":"Xingyu","family":"Zhou","sequence":"first","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Wu","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Tan","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin","family":"Sun","sequence":"additional","affiliation":[{"name":"Auburn University, Auburn, AL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ness","family":"Shroff","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-012-9305-y"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1978.1094075"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/GCE.2008.4738445"},{"key":"e_1_2_1_5_1","volume-title":"HBase: the definitive guide. \" O'Reilly Media","author":"George Lars","unstructured":"Lars George . 2011. HBase: the definitive guide. \" O'Reilly Media , Inc .\". Lars George. 2011. HBase: the definitive guide. \" O'Reilly Media, Inc.\"."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2007.06.012"},{"key":"e_1_2_1_7_1","volume-title":"Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability","author":"Hajek Bruce","year":"1982","unstructured":"Bruce Hajek . 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability ( 1982 ), 502--525. Bruce Hajek. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability (1982), 502--525."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.07.015"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.08.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652141"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2016.68"},{"key":"e_1_2_1_13_1","unstructured":"Rajesh Nishtala Hans Fugal Steven Grimm Marc Kwiatkowski Herman Lee Harry C Li Ryan McElroy Mike Paleczny Daniel Peek Paul Saab etal 2013. Scaling memcache at facebook. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 385--398.   Rajesh Nishtala Hans Fugal Steven Grimm Marc Kwiatkowski Herman Lee Harry C Li Ryan McElroy Mike Paleczny Daniel Peek Paul Saab et al. 2013. Scaling memcache at facebook. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 385--398."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2002.1023397"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-015-9448-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494232.2465757"},{"key":"e_1_2_1_17_1","first-page":"20","article-title":"Queueing system with selection of the shortest of two queues: An asymptotic approach","volume":"32","author":"Vvedenskaya Nikita Dmitrievna","year":"1996","unstructured":"Nikita Dmitrievna Vvedenskaya , Roland L'vovich Dobrushin , and Fridrikh Izrailevich Karpelevich . 1996 . Queueing system with selection of the shortest of two queues: An asymptotic approach . Problemy Peredachi Informatsii 32 , 1 (1996), 20 -- 34 . Nikita Dmitrievna Vvedenskaya, Roland L'vovich Dobrushin, and Fridrikh Izrailevich Karpelevich. 1996. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii 32, 1 (1996), 20--34.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2362745"},{"key":"e_1_2_1_19_1","volume-title":"On the optimal assignment of customers to parallel servers. Journal of Applied Probability","author":"Weber Richard R","year":"1978","unstructured":"Richard R Weber . 1978. On the optimal assignment of customers to parallel servers. Journal of Applied Probability ( 1978 ), 406--413. Richard R Weber. 1978. On the optimal assignment of customers to parallel servers. Journal of Applied Probability (1978), 406--413."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218487"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154498"}],"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\/3154498","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154498","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154498","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:27Z","timestamp":1750212687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154498"}},"subtitle":["Theory to Algorithms"],"short-title":[],"issued":{"date-parts":[[2017,12,19]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,12,19]]}},"alternative-id":["10.1145\/3154498"],"URL":"https:\/\/doi.org\/10.1145\/3154498","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,19]]},"assertion":[{"value":"2017-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}