DIMACS Discrete Math/Theory of Computing Seminar


Distributed Load Balancing: Analytical and Simulation Results


S. Muthukrishnan
University of Warwick


CoRE Building, Room 431
Busch Campus, Rutgers University


4:30 pm
Tuesday, February 20, 1996


Given an arbitrary graph in which each node has a number of tokens, the problem is to move tokens amongst the nodes in steps so each node has approximately the same number of tokens at the end. This abstracts a variety of load balancing scenarios in distributed networks and parallel finite element methods.

Depending on particular applications, one of four different models may be appropriate for the way tokens are moved in each step. We present efficient algorithms for load balancing in these models and provide tight/near-tight analyses of the algorithms. Our analyses are based on appropriate potential functions and rely on tools drawn from linear algebra. In a few cases however, we have not been able to extend these tools to analyze certain detailed aspects of these load balancing algorithms; in those cases, we have used computer simulations to gather evidence on their performance.

This talk contains material from papers in SPAA 95, STOC 95 and a few manuscripts. The coauthors are B. Ghosh, T. Leighton, B. Maggs, G. Plaxton, R. Rajaraman, A. Richa, M. Schultz, R. Tarjan, and D. Zuckerman.

Document last modified on February 14, 1996