Near-perfect load balancing by randomized rounding

ABSTRACT

We consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. The aim is minimizing the discrepancy between the maximum and minimum load. In every time-step paired processors balance their load as evenly as possible. The direction of the excess token is chosen according to a randomized rounding of the participating loads.

We prove that in comparison to the corresponding model of Rabani, Sinclair, and Wanka (1998) with arbitrary roundings, the randomization yields an improvement of roughly a square root of the achieved discrepancy in the same number of time-steps on all graphs. For the important case of expanders we can even achieve a constant discrepancy in O(log n (log log n)3) rounds. This is optimal up to loglog-factors while the best previous algorithms in this setting either require ©(log2 n) time or can only achieve a logarithmic discrepancy. Our new result also demonstrates that with randomized rounding the difference between discrete and continuous load balancing vanishes almost completely.

REFERENCES

• 1: William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167250]
• 2: H. Arndt. Load balancing: Dimension exchange on product graphs. In 18th IPDPS 04. IEEE Computer Society, 2004.
• 3: James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
• 4: Petra Berenbrink , Tom Friedetzky , Zengjian Hu, A new analytical method for parallel, diffusion-type load balancing, Journal of Parallel and Distributed Computing, v.69 n.1, p.54-61, January, 2009 [doi>10.1016/j.jpdc.2008.05.005]
• 5: Stephen Boyd , Arpita Ghosh , Balaji Prabhakar , Devavrat Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2508-2530, June 2006 [doi>10.1109/TIT.2006.874516]
• 6: Joshua N. Cooper , Joel Spencer, Simulating a Random Walk with Constant Error, Combinatorics, Probability and Computing, v.15 n.6, p.815-822, November 2006 [doi>10.1017/S0963548306007565]
• 7: R. Elsässer, B. Monien, and S. Schamberger. Distributing unit size workload packages in heterogenous networks. Journal of Graph Algorithms &#;amp; Applications, 10(1):51--68, 2006.
• 8: Uriel Feige , David Peleg , Prabhakar Raghavan , Eli Upfal, Randomized Broadcast in Networks, Proceedings of the International Symposium on Algorithms, p.128-137, August 16-18, 1990
• 9: Bhaskar Ghosh , F. T. Leighton , Bruce M. Maggs , S. Muthukrishnan , C. Greg Plaxton , R. Rajaraman , Andréa W. Richa , Robert E. Tarjan , David Zuckerman, Tight Analyses of Two Local Load Balancing Algorithms, SIAM Journal on Computing, v.29 n.1, p.29-64, Feb. 2000 [doi>10.1137/S0097539795292208]
• 10: Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing by random matchings, Journal of Computer and System Sciences, v.53 n.3, p.357-370, Dec. 1996 [doi>10.1006/jcss.1996.0075]
• 11: Maurice Herlihy , Srikanta Tirthapura, Randomized smoothing networks, Journal of Parallel and Distributed Computing, v.66 n.5, p.626-632, May 2006 [doi>10.1016/j.jpdc.2005.06.009]
• 12: Michael Richard Klugerman , Frank Thomson Leighton, Small-depth counting networks and related topics, Massachusetts Institute of Technology, 1994
• 13: Michael Klugerman , C. Greg Plaxton, Small-depth counting networks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.417-428, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129752]
• 14: László Lovász , Peter Winkler, Mixing of random walks and other diffusions on a graph, Surveys in combinatorics, 1995, Cambridge University Press, New York, NY, 1995
• 15: Reinhard Lüling , Burkhard Monien, A dynamic distributed load balancing algorithm with provable good performance, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.164-172, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165252]
• 16: Marios Mavronicolas , Thomas Sauerwald, The impact of randomization in smoothing networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400797]
• 17: S. Muthukrishnan, B. Ghosh, and M. H. Schultz. First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Theory Comput. Syst., 31(4):331--354, 1998.
• 18: Yuval Rabani , Alistair Sinclair , Rolf Wanka, Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.694, November 08-11, 1998
• 19: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 20: Raghu Subramanian , Isaac D. Scherson, An analysis of diffusive load-balancing, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.220-225, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181361]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Theory

Keywords:
load balancing, randomized rounding