{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:27Z","timestamp":1787337507198,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within $O(\\Delta \/ \\alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $O((d^2 \\log n)\/\\alpha)$, where $\\Delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\\alpha$ is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion $\\alpha$, and for any value $\\Delta$, there exists an initial distribution of tokens with imbalance $\\Delta$ for which the time to reduce the imbalance to even $\\Delta\/2$ is at least $\\Omega(\\Delta\/\\alpha)$. The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\\Omega((d^2 \\log n) \/ \\alpha)$. Furthermore, we show that upon reaching a state with a global imbalance of $O((d^2 \\log n)\/\\alpha)$, the time for this algorithm to locally balance the network can be as large as $\\Omega(n^{1\/2})$. We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.<\/jats:p>","DOI":"10.1137\/s0097539795292208","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"29-64","source":"Crossref","is-referenced-by-count":38,"title":["Tight Analyses of Two Local Load Balancing Algorithms"],"prefix":"10.1137","volume":"29","author":[{"given":"Bhaskar","family":"Ghosh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. T.","family":"Leighton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce M.","family":"Maggs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. Greg","family":"Plaxton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9a W.","family":"Richa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Y. Afek, E. Gafni, and A. Rosen,\n                      The slide mechanism with applications in dynamic networks\n                      , in Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, 1992, pp. 35\u201346.","DOI":"10.1145\/135419.135430"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"W. Aiello, B. Awerbuch, B. Maggs, and S. Rao,\n                      Approximate load balancing on dynamic and asynchronous networks\n                      , in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 632\u2013641.","DOI":"10.1145\/167088.167250"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"J. Aspnes, M. Herlihy, and N. Shavit,\n                      Counting networks and multiprocessor co\u2010ordination\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 348\u2013358.","DOI":"10.1145\/103418.103421"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and T. Leighton,\n                      A simple local\u2010control approximation algorithm for multi\u2010commodity flow\n                      , in Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science, 1993, pp. 459\u2013468.","DOI":"10.1109\/SFCS.1993.366841"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and T. Leighton,\n                      Improved approximation algorithms for the multi\u2010commodity flow problem and local competitive routing in dynamic networks\n                      , in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 487\u2013496.","DOI":"10.1145\/195058.195238"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Mansour, and N. Shavit,\n                      End\u2010to\u2010end communication with polynomial overhead\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 358\u2013363.","DOI":"10.1109\/SFCS.1989.63503"},{"key":"R8","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1989."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Andrei Broder, Alan Frieze, E. Shamir, E. Upfal, Near\u2010perfect token distribution, Lecture Notes in Comput. Sci., Vol. 623, Springer, Berlin, 1992, 308\u201331794j:68011","DOI":"10.1007\/3-540-55719-9_83"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675365"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1986.6312961"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"B. Ghosh and S. Muthukrishnan,\n                      Dynamic load balancing on parallel and distributed networks by random matchings\n                      , in Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994, pp. 226\u2013235.","DOI":"10.1145\/181014.181366"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000092"},{"key":"R16","first-page":"489","volume":"1","author":"Goldberg B.","year":"1989","journal-title":"Concurrent Computers and Applications"},{"key":"R17","unstructured":"A. Heirich and S. Taylor,\n                      A Parabolic Theory of Load Balance\n                      , Research Report Caltech\u2010CS\u2010TR\u201093\u201025, Caltech Scalable Concurrent Computation Lab, Pasadena, CA, 1993."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90182-2"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90025-K"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90081-W"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. R. Jerrum and A. Sinclair,\n                      Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 235\u2013244.","DOI":"10.1145\/62212.62234"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174145"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"M. Klugerman and C. G. Plaxton,\n                      Small depth counting networks\n                      , in Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 417\u2013428.","DOI":"10.1145\/129712.129752"},{"key":"R24","unstructured":"T. Leighton, C. E. Leiserson, and D. Kravets,\n                      Theory of Parallel and VLSI Computation\n                      , Research Seminar Series Report MIT\/LCS\/RSS 8, MIT Laboratory for Computer Science, MIT, Cambridge, MA, 1990."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1987.232563"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"R. L\u00fcling and B. Monien,\n                      Load balancing for distributed branch and bound algorithms\n                      , in Proceedings of the 6th International Parallel Processing Symposium, 1992, pp. 543\u2013549.","DOI":"10.1109\/IPPS.1992.222970"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"R. L\u00fcling and B. Monien,\n                      A dynamic distributed load balancing algorithm with provable good performance\n                      , in Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993, pp. 164\u2013172.","DOI":"10.1145\/165231.165252"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"R. L\u00fcling, B. Monien, and F. Ramme,\n                      Load balancing in large networks: A comparative study\n                      , in Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing, IEEE Press, Piscataway, NJ, 1991, pp. 686\u2013689.","DOI":"10.1109\/SPDP.1991.218196"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Friedhelm Meyer auf der Heide, Brigitte Oesterdiekhoff, Rolf Wanka, Strongly adaptive token distribution, Lecture Notes in Comput. Sci., Vol. 700, Springer, Berlin, 1993, 398\u201340994j:68016","DOI":"10.1007\/3-540-56939-1_89"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"M. Mihail,\n                      Conductance and convergence of Markov chains\u2014a combinatorial treatment of expanders\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 526\u2013531.","DOI":"10.1109\/SFCS.1989.63529"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.231863"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90069-7"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0218015"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton,\n                      Load balancing, selection and sorting on the hypercube\n                      , in Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 64\u201373.","DOI":"10.1145\/72935.72943"},{"key":"R35","first-page":"199","volume":"8","author":"Stankovic J.","year":"1984","journal-title":"Computer Networks","ISSN":"https:\/\/id.crossref.org\/issn\/1389-1286","issn-type":"print"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"R. Subramanian and I. D. Scherson,\n                      An analysis of diffusive load balancing\n                      , in Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994, pp. 220\u2013225.","DOI":"10.1145\/181014.181361"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/3149.3156"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"E. Upfal,\n                      An O(logN) deterministic packet routing scheme\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 241\u2013250.","DOI":"10.1145\/73007.73030"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030502"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1994.122"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795292208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:27Z","timestamp":1787336067000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795292208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539795292208"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795292208","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}