{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T11:41:45Z","timestamp":1787312505333,"version":"build-2736575974"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2018,3,20]]},"abstract":"<jats:p>Dynamic affinity scheduling has been an open problem for nearly three decades. The problem is to dynamically schedule multi-type tasks to multi-skilled servers such that the resulting queueing system is both stable in the capacity region (throughput optimality) and the mean delay of tasks is minimized at high loads near the boundary of the capacity region (heavy-traffic optimality). As for applications, dataintensive analytics like MapReduce, Hadoop, and Dryad fit into this setting, where the set of servers is heterogeneous for different task types, so the pair of task type and server determines the processing rate of the task. The load balancing algorithm used in such frameworks is an example of affinity scheduling which is desired to be both robust and delay optimal at high loads when hot-spots occur. Fluid model planning, the MaxWeight algorithm, and the generalized c?-rule are among the first algorithms proposed for affinity scheduling that have theoretical guarantees on being optimal in different senses, which will be discussed in the related work section. All these algorithms are not practical for use in data center applications because of their non-realistic assumptions. The join-the-shortest-queue-MaxWeight (JSQMaxWeight), JSQ-Priority, and weighted-workload algorithms are examples of load balancing policies for systems with two and three levels of data locality with a rack structure. In this work, we propose the Generalized-Balanced-Pandas algorithm (GB-PANDAS) for a system with multiple levels of data locality and prove its throughput optimality. We prove this result under an arbitrary distribution for service times, whereas most previous theoretical work assumes geometric distribution for service times. The extensive simulation results show that the GB-PANDAS algorithm alleviates the mean delay and has a better performance than the JSQMaxWeight algorithm by up to twofold at high loads. We believe that the GB-PANDAS algorithm is heavy-traffic optimal in a larger region than JSQ-MaxWeight, which is an interesting problem for future work.<\/jats:p>","DOI":"10.1145\/3199524.3199528","type":"journal-article","created":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T11:17:48Z","timestamp":1521717468000},"page":"2-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["GB-PANDAS:"],"prefix":"10.1145","volume":"45","author":[{"given":"Ali","family":"Yekkehkhany","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avesta","family":"Hojjati","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad H.","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"Johns Hopkins University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,3,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Hadoop. http:\/\/hadoop.apache.org\/. https:\/\/www.dropbox.com\/sh\/ju0fo2vadbl8nce\/AABkYePqDbmvcOzheMOLabvUa?dl=0.  Hadoop. http:\/\/hadoop.apache.org\/. https:\/\/www.dropbox.com\/sh\/ju0fo2vadbl8nce\/AABkYePqDbmvcOzheMOLabvUa?dl=0."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2011.26"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966445.1966472"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association.","author":"Ananthanarayanan Ganesh","year":"2012","unstructured":"Ganesh Ananthanarayanan , Ali Ghodsi , Andrew Wang , Dhruba Borthakur , Srikanth Kandula , Scott Shenker , and Ion Stoica . 2012 . PACMan: Coordinated memory caching for parallel jobs . In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association. Ganesh Ananthanarayanan, Ali Ghodsi, Andrew Wang, Dhruba Borthakur, Srikanth Kandula, Scott Shenker, and Ion Stoica. 2012. PACMan: Coordinated memory caching for parallel jobs. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v10-281"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1015345343"},{"key":"e_1_2_1_7_1","volume-title":"INFOCOM, 2012 Proceedings IEEE. IEEE, 1143-1151","author":"Chen Fangfei","year":"2012","unstructured":"Fangfei Chen , Murali Kodialam , and TV Lakshman . 2012 b. Joint scheduling of processing and shuffle phases in mapreduce systems . In INFOCOM, 2012 Proceedings IEEE. IEEE, 1143-1151 . Fangfei Chen, Murali Kodialam, and TV Lakshman. 2012b. Joint scheduling of processing and shuffle phases in mapreduce systems. In INFOCOM, 2012 Proceedings IEEE. IEEE, 1143-1151."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168842"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_10_1","volume-title":"Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Annals of Applied Probability","author":"Harrison J Michael","year":"1998","unstructured":"J Michael Harrison . 1998. Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Annals of Applied Probability ( 1998 ), 822-848. J Michael Harrison. 1998. Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Annals of Applied Probability (1998), 822-848."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019188531950"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2011.16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2012.122"},{"key":"e_1_2_1_14_1","first-page":"59","article-title":"Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, Vol. 41","author":"Isard Michael","year":"2007","unstructured":"Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , and Dennis Fetterly . 2007 . Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, Vol. 41 . ACM , 59 - 72 . Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, Vol. 41. ACM, 59-72.","journal-title":"ACM"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629601"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2007336.2007338"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2010.112"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003977.3003990"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2013.08.013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.07.015"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0152"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154580.3154595"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2016.019"},{"key":"e_1_2_1_24_1","volume-title":"Encyclopedia of parallel computing","author":"Padua David","unstructured":"David Padua . 2011. Encyclopedia of parallel computing . Springer Science & Business Media . David Padua. 2011. Encyclopedia of parallel computing. Springer Science & Business Media."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25821-3_10"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 17th ACM Symposium on Operating Systems Principles. 29-43","author":"Sanjay Ghemawat","year":"2003","unstructured":"Ghemawat Sanjay , Gobio? Howard, and Leung Shun-Tak . 2003 . The Google file system . In Proceedings of the 17th ACM Symposium on Operating Systems Principles. 29-43 . Ghemawat Sanjay, Gobio? Howard, and Leung Shun-Tak. 2003. The Google file system. In Proceedings of the 17th ACM Symposium on Operating Systems Principles. 29-43."},{"key":"e_1_2_1_27_1","volume-title":"Communication networks: an optimization, control, and stochastic networks perspective","author":"Srikant Rayadurgam","unstructured":"Rayadurgam Srikant and Lei Ying . 2013. Communication networks: an optimization, control, and stochastic networks perspective . Cambridge University Press . Rayadurgam Srikant and Lei Ying. 2013. Communication networks: an optimization, control, and stochastic networks perspective. Cambridge University Press."},{"key":"e_1_2_1_28_1","volume-title":"Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals of Applied Probability","author":"Stolyar Alexander L","year":"2004","unstructured":"Alexander L Stolyar . 2004. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals of Applied Probability ( 2004 ), 1-53. Alexander L Stolyar. 2004. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals of Applied Probability (2004), 1-53."},{"key":"e_1_2_1_29_1","unstructured":"Ali Yekkehkhany. 2017. Near Data Scheduling for Data Centers with Multi Levels of Data Locality. In arXiv preprint arXiv:1702.07802.  Ali Yekkehkhany. 2017. Near Data Scheduling for Data Centers with Multi Levels of Data Locality. In arXiv preprint arXiv:1702.07802 ."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566958"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2362745"},{"key":"e_1_2_1_32_1","volume-title":"Hadoop: The Definitive Guide, Yahoo.","author":"White Tom","year":"2010","unstructured":"Tom White . 2010 . Hadoop: The Definitive Guide, Yahoo. (2010). Tom White. 2010. Hadoop: The Definitive Guide, Yahoo. (2010)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218468"},{"key":"e_1_2_1_35_1","volume-title":"Pandas: Robust Locality-Aware Scheduling With Stochastic Delay Optimality","author":"Xie Qiaomin","year":"2016","unstructured":"Qiaomin Xie , Mayank Pundir , Yi Lu , Cristina L Abad , and Roy H Campbell . 2016 a. Pandas: Robust Locality-Aware Scheduling With Stochastic Delay Optimality . IEEE\/ACM Transactions on Networking ( 2016). Qiaomin Xie, Mayank Pundir, Yi Lu, Cristina L Abad, and Roy H Campbell. 2016a. Pandas: Robust Locality-Aware Scheduling With Stochastic Delay Optimality. IEEE\/ACM Transactions on Networking (2016)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524416"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1755913.1755940"},{"key":"e_1_2_1_38_1","first-page":"7","article-title":"Improving MapReduce performance in heterogeneous environments","volume":"8","author":"Zaharia Matei","year":"2008","unstructured":"Matei Zaharia , Andy Konwinski , Anthony D Joseph , Randy H Katz , and Ion Stoica . 2008 . Improving MapReduce performance in heterogeneous environments . In Osdi , Vol. 8. 7 . Matei Zaharia, Andy Konwinski, Anthony D Joseph, Randy H Katz, and Ion Stoica. 2008. Improving MapReduce performance in heterogeneous environments. In Osdi, Vol. 8. 7.","journal-title":"Osdi"},{"key":"e_1_2_1_39_1","volume-title":"Mark S Squillante, and Tonghoon Suk.","author":"Lu Yingdong","year":"2017","unstructured":"Yingdong Lu , Siva Theja Maguluri , Mark S Squillante, and Tonghoon Suk. 2017 . On Optimal Weighted-Delay Scheduling in Input-Queued Switches. In arXiv preprint arXiv:1704.02302. Yingdong Lu, Siva Theja Maguluri, Mark S Squillante, and Tonghoon Suk. 2017. On Optimal Weighted-Delay Scheduling in Input-Queued Switches. In arXiv preprint arXiv:1704.02302."}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199524.3199528","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199524.3199528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:07:17Z","timestamp":1750259237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199524.3199528"}},"subtitle":["Throughput and heavy-traffic optimality analysis for affinity scheduling"],"short-title":[],"issued":{"date-parts":[[2018,3,20]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3,20]]}},"alternative-id":["10.1145\/3199524.3199528"],"URL":"https:\/\/doi.org\/10.1145\/3199524.3199528","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2018,3,20]]},"assertion":[{"value":"2018-03-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}