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.