Abstract
This work studies distributed algorithms for locally optimal load-balancing: We are given a graph of maximum degree \(\varDelta \), and each node has up to L units of load. The task is to distribute the load more evenly so that the loads of adjacent nodes differ by at most 1. If the graph is a path (\(\varDelta = 2\)), it is easy to solve the fractional version of the problem in O(L) communication rounds, independently of the number of nodes. We show that this is tight, and we show that it is possible to solve also the discrete version of the problem in O(L) rounds in paths. For the general case (\(\varDelta > 2\)), we show that fractional load balancing can be solved in \({{\mathrm{poly}}}(L,\varDelta )\) rounds and discrete load balancing in \(f(L,\varDelta )\) rounds for some function f, independently of the number of nodes.
See the full version of this work [10] for detailed proofs and additional illustrations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Awerbuch, B., Maggs, B., Rao, S.: Approximate load balancing on dynamic and asynchronous networks. In: Proc. 25th Annual ACM Symposium on Theory of Computing (STOC 1993), pp. 632–641. ACM Press (1993). doi:10.1145/167088.167250
Anderson, R., Lovász, L., Shor, P., Spencer, J., Tardos, E., Winograd, S.: Disks, balls, and walls: analysis of a combinatorial game. The American Mathematical Monthly 96(6), 481–493 (1989). http://www.jstor.org/stable/2323970
Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM Journal on Computing 29(1), 180–200 (1999). doi:10.1137/S0097539795288490
Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality: An explanation of the \(1/f\) noise. Physical Review Letters 59(4), 381–384 (1987). doi:10.1103/PhysRevLett.59.381
Bogdan, P., Sauerwald, T., Stauffer, A., He, S.: Balls into bins via local search. In: Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 16–34. SIAM (2013). doi:10.1137/1.9781611973105
Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Transactions on Information Theory 52(6), 2508–2530 (2006). doi:10.1109/TIT.2006.874516
Bringmann, K., Sauerwald, T., Stauffer, A., Sun, H.: Balls into bins via local search: cover time and maximum loads. In: Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 187–198 (2014). doi:10.4230/LIPIcs.STACS.2014.187
Czygrinow, A., Hanćkowiak, M., Szymańska, E., Wawrzyniak, W.: Distributed 2-approximation algorithm for the semi-matching problem. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 210–222. Springer, Heidelberg (2012)
Dhar, D.: Theoretical studies of self-organized criticality. Physica A 369(1), 29–70 (2006). doi:10.1016/j.physa.2006.04.004
Feuilloley, L., Hirvonen, J., Suomela, J.: Locally optimal load balancing (2015). http://arxiv.org/abs/1502.04511
Floréen, P., Kaski, P., Polishchuk, V., Suomela, J.: Almost stable matchings by truncating the Gale-Shapley algorithm. Algorithmica 58(1), 102–118 (2010). doi:10.1007/s00453-009-9353-9. http://arxiv.org/abs/0812.4893
Ghosh, B., Leighton, F.T., Maggs, B., Muthukrishnan, S., Plaxton, C.G., Rajaraman, R., Richa, A.W., Tarjan, R.E., Zuckerman, D.: Tight analyses of two local load balancing algorithms. SIAM Journal on Computing 29(1), 29–64 (1999)
Ghosh, B., Muthukrishnan, S.: Dynamic load balancing by random matchings. Journal of Computer and System Sciences 53(3), 357–370 (1996). doi:10.1006/jcss.1996.0075
Hańćkowiak, M., Karoński, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 219–225. SIAM (1998)
Harvey, N.J.A., Ladner, R.E., Lovász, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing. Journal of Algorithms 59(1), 53–78 (2006). doi:10.1016/j.jalgor.2005.01.003
Kadanoff, L.P., Nagel, S.R., Wu, L., Zhou, S.M.: Scaling and universality in avalanches. Physical Review A 39(12), 6524–6537 (1989). doi:10.1103/PhysRevA.39.6524
Karp, R.M., Luby, M., Meyer auf der Heide, F.: Efficient PRAM simulation on a distributed memory machine. Algorithmica 16(4–5), 517–542 (1996). doi:10.1007/s004539900063
Kenthapadi, K., Panigrahy, R.: Balanced allocation on graphs. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA 2006), pp. 434–443. SIAM (2006). doi:10.1145/1109557.1109606. http://arxiv.org/abs/cs/0510086
Khuller, S., Vishkin, U., Young, N.: A primal-dual parallel approximation technique applied to weighted set and vertex covers. Journal of Algorithms 17(2), 280–289 (1994). doi:10.1006/jagm.1994.1036
Muthukrishnan, S., Ghosh, B., Schultz, M.H.: First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Theory of Computing Systems 31(4), 331–354 (1998). doi:10.1007/s002240000092
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)
Peleg, D., Upfal, E.: The token distribution problem. SIAM Journal on Computing 18(2), 229–243 (1989). doi:10.1137/0218015
Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of Markov chains and the analysis of iterative load-balancing schemes. In: Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), p. 694. IEEE (1998). doi:10.1109/SFCS.1998.743520
Sauerwald, T., Sun, H.: Tight bounds for randomized load balancing on arbitrary network topologies. In: Proc. 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), pp. 341–350. IEEE, October 2012. doi:10.1109/FOCS.2012.86
Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82(1), 93–133 (1989). doi:10.1016/0890-5401(89)90067-9
Vöcking, B.: How asymmetry helps load balancing. Journal of the ACM 50(4), 568–589 (2003). doi:10.1145/792538.792546
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feuilloley, L., Hirvonen, J., Suomela, J. (2015). Locally Optimal Load Balancing. In: Moses, Y. (eds) Distributed Computing. DISC 2015. Lecture Notes in Computer Science(), vol 9363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48653-5_36
Download citation
DOI: https://doi.org/10.1007/978-3-662-48653-5_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48652-8
Online ISBN: 978-3-662-48653-5
eBook Packages: Computer ScienceComputer Science (R0)