We study the problem of balancing the load on processors of an arbitrary network. If jobs arrive or depart during the process of load balancing, we have the dynamic load balancing problem; otherwise, we have the static load balancing problem. While static load balancing on arbitrary and special networks has been well studied, very little is known about dynamic load balancing. The difficulty lies in modeling the arrivals and departures of jobs in a clean manner.
In this paper, we initiate the study of dynamic load balancing by
modeling job traffic using an adversary. Our main result is that a
simple, local control distributed load balancing algorithm maintains
the load of the network within a stable level against this powerful
adversary. Our results hold for different models of traffic patterns
and processor communication.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-40.ps.gz
DIMACS Home Page