DIMACS Discrete Math/Theory of Computing Seminar


Title:

Distributed Load Balancing: Analytical and Simulation Results

Speaker:

S. Muthukrishnan
University of Warwick

Place:

CoRE Building, Room 431
Busch Campus, Rutgers University

Time:

4:30 pm
Tuesday, February 20, 1996

Abstract:

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.


dimacs-www@dimacs.rutgers.edu
Document last modified on February 14, 1996