Abstract
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.
Original language | English (US) |
---|---|
Pages | 47-54 |
Number of pages | 8 |
DOIs | |
State | Published - 1998 |
Event | Proceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA - Puerto Vallarta, Mexico Duration: Jun 28 1998 → Jul 2 1998 |
Conference
Conference | Proceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA |
---|---|
City | Puerto Vallarta, Mexico |
Period | 6/28/98 → 7/2/98 |
ASJC Scopus subject areas
- Software
- Safety, Risk, Reliability and Quality