{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T05:47:54Z","timestamp":1751348874265,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2-4","license":[{"start":{"date-parts":[[2022,11,26]],"date-time":"2022-11-26T00:00:00Z","timestamp":1669420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"U.S. ARL and the U.K. MoD","award":["W911NF-16-3-0001"],"award-info":[{"award-number":["W911NF-16-3-0001"]}]},{"name":"NSF","award":["CNS-1617437"],"award-info":[{"award-number":["CNS-1617437"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Distributed load balancing is the act of allocating jobs among a set of servers as evenly as possible. The static interpretation of distributed load balancing leads to formulating the load-balancing problem as a classical balls-and-bins problem with jobs (balls) never leaving the system and accumulating at the servers (bins). While most of the previous work in the static setting focus on studying the maximum number of jobs allocated to a server or\n            <jats:italic>maximum load<\/jats:italic>\n            , little importance has been given to the\n            <jats:italic>implementation cost<\/jats:italic>\n            , or the cost of moving a job\/data to\/from its allocated server, for such policies.\n          <\/jats:p>\n          <jats:p>\n            This article designs and evaluates server proximity aware static load-balancing policies with a goal to reduce the\n            <jats:italic>implementation cost<\/jats:italic>\n            . We consider a class of proximity aware Power of Two (POT) choice-based assignment policies for allocating jobs to servers, where both jobs and servers are located on a two-dimensional Euclidean plane. In this framework, we investigate the tradeoff between the implementation cost and load-balancing performance of different allocation policies. To this end, we first design and evaluate a\n            <jats:italic>Spatial Power of two<\/jats:italic>\n            (sPOT) policy in which each job is allocated to the least loaded server among its two geographically nearest servers. We provide expressions for the lower bound on the asymptotic expected maximum load on the servers and prove that sPOT does not achieve classical POT load-balancing benefits. However, experimental results suggest the efficacy of sPOT with respect to expected implementation cost. We also propose two non-uniform server sampling-based POT policies that achieve the best of both implementation cost and load-balancing performance.\n          <\/jats:p>\n          <jats:p>\n            We then extend our analysis to the case where servers are interconnected as an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G(S, E)<\/jats:italic>\n            . We assume each job arrives at one of the servers,\n            <jats:italic>u,<\/jats:italic>\n            chosen uniformly at random from the vertex set\n            <jats:italic>S.<\/jats:italic>\n            We then assign each job to the server with minimum load among servers\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            where\n            <jats:italic>v<\/jats:italic>\n            is chosen according to one of the following two policies: (i) Unif-POT(\n            <jats:italic>k<\/jats:italic>\n            ): Sample a server\n            <jats:italic>v<\/jats:italic>\n            uniformly at random from\n            <jats:italic>k<\/jats:italic>\n            -hop neighborhood of\n            <jats:italic>u;<\/jats:italic>\n            (ii) InvSq-POT(\n            <jats:italic>k<\/jats:italic>\n            ): Sample a server\n            <jats:italic>v<\/jats:italic>\n            from\n            <jats:italic>k<\/jats:italic>\n            -hop neighborhood of\n            <jats:italic>u<\/jats:italic>\n            with probability proportional to the inverse square of the distance between\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            . An extensive simulation over a wide range of topologies validates the efficacy of both the policies. Our simulation results show that both policies consistently produce a load distribution that is much similar to that of a classical POT. Depending on topology, we observe the total variation distance to be of the order of 0.002\u20130.08 for both the policies while achieving a 8%\u201399% decrease in implementation cost as compared to the classical POT.\n          <\/jats:p>","DOI":"10.1145\/3549933","type":"journal-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T12:20:30Z","timestamp":1658406030000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Analysis and Evaluation of Proximity-based Load-balancing Policies"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9859-6794","authenticated-orcid":false,"given":"Nitish K.","family":"Panigrahy","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4539-2701","authenticated-orcid":false,"given":"Thirupathaiah","family":"Vasantam","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8295-1878","authenticated-orcid":false,"given":"Prithwish","family":"Basu","sequence":"additional","affiliation":[{"name":"Raytheon BBN Technologies, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7808-7375","authenticated-orcid":false,"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1439-332X","authenticated-orcid":false,"given":"Ananthram","family":"Swami","sequence":"additional","affiliation":[{"name":"Army Research Laboratory, Adelphi, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3860-6257","authenticated-orcid":false,"given":"Kin K.","family":"Leung","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<159::AID-RSA3>3.0.CO;2-Q"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.05.010"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_2_6_2","volume-title":"Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN)","author":"Bash B. A.","year":"2007","unstructured":"B. A. Bash and P. J. Desnoyers. 2007. Exact distributed Voronoi cell computation in sensor networks. In Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN)."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444435X"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20602"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1214\/18-AAP1437"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007921"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400232"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007978"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6940-7_15"},{"key":"e_1_3_2_15_2","first-page":"601","article-title":"On the connectivity of dynamic random geometric graphs","author":"Diaz J.","year":"2008","unstructured":"J. Diaz, D. Mitsche, and X. Perez-Gimenez. 2008. On the connectivity of dynamic random geometric graphs. In Proceedings of the Symposium on Discrete Algorithms. 601\u2013610.","journal-title":"I"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP898"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.056110"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825263"},{"key":"e_1_3_2_19_2","first-page":"511","article-title":"Balls and bins with structure: Balanced allocations on hypergraphs","author":"Godfrey P. Brighten","year":"2008","unstructured":"P. Brighten Godfrey. 2008. Balls and bins with structure: Balanced allocations on hypergraphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 511\u2013517.","journal-title":"I"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.11"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109606"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2013.04.009"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"K. Kenthapadi and R. Panigrahy. 2005. Balanced allocation on graphs. Retrieved from: http:\/\/arxiv.org\/abs\/cs\/0510086.","DOI":"10.1145\/1109557.1109606"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_3_2_25_2","volume-title":"Academic Press","author":"Marshall A. W.","year":"1979","unstructured":"A. W. Marshall and I. Olkin. 1979. Inequalities: Theory of Majorization and Its Applications. Academic Press."},{"key":"e_1_3_2_26_2","volume-title":"Ph.D. Dissertation. Harvard University","author":"Mitzenmacher M. D.","year":"1996","unstructured":"M. D. Mitzenmacher. 1996. The Power of Two Choices in Randomized Load Balancing. Ph.D. Dissertation. Harvard University."},{"key":"e_1_3_2_27_2","volume-title":"Wiley, New York","author":"Okabe A.","year":"1992","unstructured":"A. Okabe, B. Boots, and K. Sugihara. 1992. Spatial Tessellations Concepts and Applications of Voronoi Diagrams. Wiley, New York."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20558"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20875"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.24"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21712"},{"key":"e_1_3_2_33_2","volume-title":"arXiv:2008.07562","author":"Rutten D.","year":"2020","unstructured":"D. Rutten and D. Mukherjee. 2020. Load balancing under strict compatibility constraints. arXiv:2008.07562."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2018.8635943"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/s0269964800005088"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"issue":"1","key":"e_1_3_2_37_2","first-page":"20","article-title":"Queueing system with selection of the shortest of two queues: An asymptotic approach","volume":"32","author":"Vvedenskaya N. D.","year":"1996","unstructured":"N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. 1996. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii 32, 1 (1996), 20\u201334.","journal-title":"Problemy Peredachi Informatsii"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549933","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549933","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:13Z","timestamp":1750183693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,26]]},"references-count":36,"journal-issue":{"issue":"2-4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3549933"],"URL":"https:\/\/doi.org\/10.1145\/3549933","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2022,11,26]]},"assertion":[{"value":"2021-03-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}