Adversarial model for distributed dynamic load balancing

S. Muthukrishnan, R. Rajaraman

    Research output: Contribution to conferencePaperpeer-review

    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 languageEnglish (US)
    Pages47-54
    Number of pages8
    DOIs
    StatePublished - 1998
    EventProceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA - Puerto Vallarta, Mexico
    Duration: Jun 28 1998Jul 2 1998

    Conference

    ConferenceProceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA
    CityPuerto Vallarta, Mexico
    Period6/28/987/2/98

    ASJC Scopus subject areas

    • Software
    • Safety, Risk, Reliability and Quality

    Fingerprint

    Dive into the research topics of 'Adversarial model for distributed dynamic load balancing'. Together they form a unique fingerprint.

    Cite this