Load balancing of unit size tokens and expansion properties of graphs

ABSTRACT

Diffusive schemes have been widely analyzed for parallel and distributed load balancing. It is well known that their convergence rates depend on the eigenvalues of some associated matrices and on the expansion properties of the underlying graphs. In the first part of this paper we make use of these relationships in order to obtain new spectral bounds on the edge and node expansion of graphs. We show that these new bounds are better than the classical bounds for several graph classes. In the second part of the paper, we consider the load balancing problem for indivisible unit size tokens. Since known diffusion schemes do not completely balance the load for such settings, we propose a randomized distributed algorithm based on Markov chains to reduce the load imbalance. We prove that this approach provides the best asymptotic result that can be achieved in l1- or l2-norm concerning the final load situation.

REFERENCES

• 1: D. Aldous. On the markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probab. Engrg. Inform. Sci., 1:33--46, 1987.
• 2: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 3: N. Alon , Z. Galil , V. D. Milman, Better expanders and superconcentrators, Journal of Algorithms, v.8 n.5, p.337-347, Sept. 1987 [doi>10.1016/0196-6774(87)90014-9]
• 4: N. Alon and V. Milman. λ1, isoperimetric inequalities for graphs, and superconcentrators. J. of Combin. Theory, B(38):73--88, 1985.
• 5: J. E. Boillat, Load balancing and Poisson equation in a graph, Concurrency: Practice and Experience, v.2 n.4, p.289-313, Dec. 1990 [doi>10.1002/cpe.4330020403]
• 6: J. Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis, pages 195--199, 1970.
• 7: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat., 23:493--507, 1952.
• 8: F. Chung. Spectral Graph Theory, volume 92 of CBMS Regional conference series in mathematics. American Mathematical Society, 1997.
• 9: A. Cortés , A. Ripoll , F. Cedó , M. A. Senar , E. Luque, An asynchronous and iterative load balancing algorithm for discrete load model, Journal of Parallel and Distributed Computing, v.62 n.12, p.1729-1746, December 2002 [doi>10.1016/S0743-7315(02)00006-0]
• 10: G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
• 11: Ralf Diekmann , Andreas Frommer , Burkhard Monien, Efficient schemes for nearest neighbor load balancing, Parallel Computing, v.25 n.7, p.789-812, July 1999 [doi>10.1016/S0167-8191(99)00018-6]
• 12: R. Elsásser, B. Monien, and R. Preis. Diffusion schemes for load balancing on heterogeneous networks. Theory of Computing Systems, 35:305--320, 2002.
• 13: J. Fill. Eigenvalue bounds on convergence to stationarity for nonreversible markov chains with an application to the exclusion process. Annals of Applied Probability, 1:62--87, 1991.
• 14: G. Fox, R. Williams, and P. Messina. Parallel Computing Works! Morgan Kaufmann, 1994.
• 15: 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]
• 16: David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
• 17: G. Golub. Bounds for the round-off errors in the richardson second order method, BIT, 2:212--223, 1962.
• 18: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 19: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 20: Nabil Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM (JACM), v.42 n.5, p.1091-1106, Sept. 1995 [doi>10.1145/210118.210136]
• 21: L. Lovász and M. Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms, 4:359--412, 1993.
• 22: M. Mihail. Conductance and convergence of markov chains: a combinatorial treatment of expanders. In Proc. of the 37th Conf. on Foundations of Computer Science, pages 526--531, 1989.
• 23: B. Mohar. Isoperimetric inequalities, growth, and the spectrum of graphs. Lin. Alg. Appl., 103:119--131, 1988.
• 24: B. Mohar, Isoperimetric numbers of graphs, Journal of Combinatorial Theory Series B, v.47 n.3, p.274-291, Dec. 1989 [doi>10.1016/0095-8956(89)90029-4]
• 25: S. Muthukrishnan, B. Ghosh, and M. Schultz. First and second order diffusive methods for rapid, coarse, distributed load balancing. Theory of Computing Systems, 31:331--354, 1998.
• 26: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 27: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 28: 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
• 29: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 30: R. Tanner. Explicit construction of concentrators from generalized n-gons. Algebraic Discrete Methods, 5:287--294, 1984.