{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:48Z","timestamp":1740109308829,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T00:00:00Z","timestamp":1640304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T00:00:00Z","timestamp":1640304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["PR1042ERC01"],"award-info":[{"award-number":["PR1042ERC01"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Institute of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the following dynamic load-balancing process: given an underlying graph<jats:italic>G<\/jats:italic>with<jats:italic>n<\/jats:italic>nodes, in each step<jats:inline-formula><jats:alternatives><jats:tex-math>$$t\\ge 0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>t<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, the two nodes<jats:italic>balance<\/jats:italic>their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on<jats:italic>n<\/jats:italic>and on the graph structure. Peres et\u00a0al.\u00a0(Random Struct Algorithms 47(4):760\u2013775, 2015) studied the variant of this process, where the unit of load is placed in the least loaded endpoint of the chosen edge, and the averaging is not performed. In the case of dynamic load balancing on the cycle of length<jats:italic>n<\/jats:italic>the only known upper bound on the expected gap is of order<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}( n \\log n )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, following from the majorization argument due to the same work. In this paper, we leverage the power of averaging and provide an improved upper bound of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O} ( \\sqrt{n} \\log n )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msqrt><mml:mi>n<\/mml:mi><\/mml:msqrt><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We introduce a new potential analysis technique, which enables us to bound the difference in load between<jats:italic>k<\/jats:italic>-hop neighbors on the cycle, for any<jats:inline-formula><jats:alternatives><jats:tex-math>$$k \\le n\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>k<\/mml:mi><mml:mo>\u2264<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>\/<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We complement this with a \u201cgap covering\u201d argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We also show that our analysis can be extended to the specific instance of Harary graphs. On the other hand, we prove that the expected second moment of the gap is lower bounded by<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03a9<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor.<\/jats:p>","DOI":"10.1007\/s00453-021-00905-9","type":"journal-article","created":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T14:02:17Z","timestamp":1640354537000},"page":"1007-1029","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Averaging Load Balancing on Cycles"],"prefix":"10.1007","volume":"84","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5634-0731","authenticated-orcid":false,"given":"Giorgi","family":"Nadiradze","sequence":"additional","affiliation":[]},{"given":"Amirmojtaba","family":"Sabour","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,24]]},"reference":[{"key":"905_CR1","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Brown, T., Kopinsky, J., Li, J.Z., Nadiradze, G.: Distributionally linearizable data structures. arXiv preprint arXiv:1804.01018 (2018)","DOI":"10.1145\/3210377.3210411"},{"key":"905_CR2","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Kopinsky, J., Li, J., Nadiradze, G.: The power of choice in priority scheduling. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 283\u2013292. ACM (2017)","DOI":"10.1145\/3087801.3087810"},{"issue":"1","key":"905_CR3","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y Azar","year":"1999","unstructured":"Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM J. Comput. 29(1), 180\u2013200 (1999)","journal-title":"SIAM J. Comput."},{"key":"905_CR4","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: the heavily loaded case. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC\u201900, New York, NY, USA. ACM, pp. 745\u2013754 (2000)","DOI":"10.1145\/335305.335411"},{"key":"905_CR5","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Friedetzky, T., Hu, Z.: A new analytical method for parallel, diffusion-type load balancing. vol. 2006 (2006)","DOI":"10.1109\/IPDPS.2006.1639292"},{"key":"905_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/cpe.4330020403","volume":"2","author":"JE Boillat","year":"1990","unstructured":"Boillat, J.E.: Load balancing and Poisson equation in a graph. Concurr. Pract. Exp. 2, 289\u2013314 (1990)","journal-title":"Concurr. Pract. Exp."},{"issue":"SI","key":"905_CR7","first-page":"2508","volume":"14","author":"S Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE\/ACM Trans. Netw. 14(SI), 2508\u20132530 (2006)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"905_CR8","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Stemann, V.: Randomized allocation processes. In: Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE, pp. 194\u2013203 (1997)","DOI":"10.1109\/SFCS.1997.646108"},{"key":"905_CR9","doi-asserted-by":"crossref","unstructured":"Frieze, A., Melsted, P., Mitzenmacher, M.: An analysis of random-walk cuckoo hashing. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, pp. 490\u2013503 (2009)","DOI":"10.1007\/978-3-642-03685-9_37"},{"key":"905_CR10","doi-asserted-by":"crossref","unstructured":"Ghosh, B., Leighton, F., Maggs, B., Muthukrishnan, S., Plaxton, C., Rajaraman, R., Richa, A., Tarjan, R., Zuckerman, D.: Tight analyses of two local load balancing algorithms, vol. 29, pp. 548\u2013558 (1995)","DOI":"10.1145\/225058.225272"},{"issue":"3","key":"905_CR11","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1006\/jcss.1996.0075","volume":"53","author":"B Ghosh","year":"1996","unstructured":"Ghosh, B., Muthukrishnan, S.: Dynamic load balancing by random matchings. J. Comput. Syst. Sci. 53(3), 357\u2013370 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"905_CR12","doi-asserted-by":"crossref","unstructured":"Ghosh, B., Muthukrishnan, S., Schultz, M.H.: First and second order diffusive methods for rapid, coarse, distributed load balancing (extended abstract). In: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA\u201996, New York, NY, USA. Association for Computing Machinery, pp. 72\u201381 (1996)","DOI":"10.1145\/237502.237509"},{"issue":"7","key":"905_CR13","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1073\/pnas.48.7.1142","volume":"48","author":"F Harary","year":"1962","unstructured":"Harary, F.: The maximum connectivity of a graph. Proc. Natl. Acad. Sci. USA 48(7), 1142 (1962)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"10","key":"905_CR14","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1109\/71.963420","volume":"12","author":"M Mitzenmacher","year":"2001","unstructured":"Mitzenmacher, M.: The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst. 12(10), 1094\u20131104 (2001)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"4","key":"905_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s002240000092","volume":"31","author":"S Muthukrishnan","year":"1998","unstructured":"Muthukrishnan, S., Ghosh, B., Schultz, M.H.: First-and second-order diffusive methods for rapid, coarse, distributed load balancing. Theory Comput. Syst. 31(4), 331\u2013354 (1998)","journal-title":"Theory Comput. Syst."},{"key":"905_CR16","unstructured":"Peres, Y.: Personal Communication (2015)"},{"issue":"4","key":"905_CR17","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1002\/rsa.20558","volume":"47","author":"Y Peres","year":"2015","unstructured":"Peres, Y., Talwar, K., Wieder, U.: Graphical balanced allocations and the (1+ $$\\beta $$)-choice process. Random Struct. Algorithms 47(4), 760\u2013775 (2015)","journal-title":"Random Struct. Algorithms"},{"key":"905_CR18","doi-asserted-by":"crossref","unstructured":"Raab, M., Steger, A.: \u201cballs into bins\u201d\u2014a simple and tight analysis. In: International Workshop on Randomization and Approximation Techniques in Computer Science. Springer, pp. 159\u2013170 (1998)","DOI":"10.1007\/3-540-49543-6_13"},{"key":"905_CR19","doi-asserted-by":"crossref","unstructured":"Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of Markov chains and the analysis of iterative load-balancing schemes. In: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pp. 694\u2013703 (1998)","DOI":"10.1109\/SFCS.1998.743520"},{"key":"905_CR20","first-page":"255","volume":"9","author":"AW Richa","year":"2001","unstructured":"Richa, A.W., Mitzenmacher, M., Sitaraman, R.: The power of two random choices: a survey of techniques and results. Comb. Optim. 9, 255\u2013304 (2001)","journal-title":"Comb. Optim."},{"key":"905_CR21","doi-asserted-by":"crossref","unstructured":"Sauerwald, T., Sun, H.: Tight bounds for randomized load balancing on arbitrary network topologies. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, pp. 341\u2013350 (2012)","DOI":"10.1109\/FOCS.2012.86"},{"issue":"1","key":"905_CR22","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A Sinclair","year":"1989","unstructured":"Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82(1), 93\u2013133 (1989)","journal-title":"Inf. Comput."},{"key":"905_CR23","unstructured":"Talwar, K., Wieder, U.: Balanced allocations: a simple proof for the heavily loaded case. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science. Springer, pp. 979\u2013990 (2014)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00905-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00905-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00905-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T05:07:55Z","timestamp":1726376875000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00905-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,24]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["905"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00905-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,12,24]]},"assertion":[{"value":"17 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}