{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T06:37:40Z","timestamp":1773729460945,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"cluster SysNum"},{"name":"project ANR DESCARTES","award":["ANR-16-CE40-0023"],"award-info":[{"award-number":["ANR-16-CE40-0023"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            We consider the problem of deterministic load balancing of tokens in the discrete model. A set of\n            <jats:italic>n<\/jats:italic>\n            processors is connected into a\n            <jats:italic>d<\/jats:italic>\n            -regular undirected network. In every timestep, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible.\n          <\/jats:p>\n          <jats:p>\n            In this work, we identify some natural conditions on deterministic load-balancing algorithms to improve upon the long-standing results of Rabani et al. (1998). Specifically, we introduce the notion of\n            <jats:italic>cumulatively fair<\/jats:italic>\n            load-balancing algorithms where in any interval of consecutive timesteps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms that are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            min { \u221a log\n            <jats:italic>n<\/jats:italic>\n            \/\u03bc,\u221a\n            <jats:italic>n<\/jats:italic>\n            }) in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>T<\/jats:italic>\n            ), where \u03bc is the spectral gap of the transition matrix of the graph. We also show that, in general, neither of these assumptions may be omitted without increasing discrepancy. We then show, by a combinatorial potential reduction argument, that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            ) almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.\n          <\/jats:p>","DOI":"10.1145\/3282435","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Improved Analysis of Deterministic Load-Balancing Schemes"],"prefix":"10.1145","volume":"15","author":[{"given":"Petra","family":"Berenbrink","sequence":"first","affiliation":[{"name":"Hamburg University, Hamburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[{"name":"CNRS\u2014LaBRI\u2014Universit\u00e9 de Bordeaux, Talence cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Kosowski","sequence":"additional","affiliation":[{"name":"Inria\u2014IRIF\u2014Paris Diderot University, Paris Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederik","family":"Mallmann-Trenn","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Przemys\u0142aw","family":"Uzna\u0144ski","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332460"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.78"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486178"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0266-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.027"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1853992.1853997"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007565"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009589"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799216"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536433"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.37236\/439"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20533"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"A. Kosowski and D. Pajak. 2014. Does adding more agents make a difference? A case study of cover time for the rotor-router. In ICALP. 544--555.  A. Kosowski and D. Pajak. 2014. Does adding more agents make a difference? A case study of cover time for the rotor-router. In ICALP. 544--555.","DOI":"10.1007\/978-3-662-43951-7_46"},{"key":"e_1_2_1_14_1","unstructured":"D. Levin Y. Peres and E. Wilmer. 2006. Markov Chains and Mixing Times. American Mathematical Society.  D. Levin Y. Peres and E. Wilmer. 2006. Markov Chains and Mixing Times. American Mathematical Society."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000074"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.77.5079"},{"key":"e_1_2_1_17_1","unstructured":"Y. Rabani A. Sinclair and R. Wanka. 1998. Local divergence of Markov chains and the analysis of iterative load balancing schemes. In FOCS. 694--705.   Y. Rabani A. Sinclair and R. Wanka. 1998. Local divergence of Markov chains and the analysis of iterative load balancing schemes. In FOCS. 694--705."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.86"},{"key":"e_1_2_1_19_1","unstructured":"T. Shiraga Y. Yamauchi S. Kijimam and M. Yamashita. 2013. Deterministic random walks for rapidly mixing chains. arXiv:1311.3749.  T. Shiraga Y. Yamauchi S. Kijimam and M. Yamashita. 2013. Deterministic random walks for rapidly mixing chains. arXiv:1311.3749."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181361"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1030-9"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282435","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3282435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:29Z","timestamp":1750208249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3282435"],"URL":"https:\/\/doi.org\/10.1145\/3282435","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}