# 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.

Document last modified on February 14, 1996