Dynamic load balancing by random matchings

Bhaskar Ghosh, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review


    The fundamental problems in dynamic load balancing and job scheduling in parallel and distributed networks involve moving load between processors. In this paper we consider a new model for load movement in synchronous machines. In each step of our model, load can be moved across only a matching set of communication links but across each link any amount of load can be moved. We present an efficient local algorithm for the dynamic load balancing problem under our model of load movement. Our algorithm works on networks of arbitrary topology under possible failure of links. The running time of our algorithm is related to the eigenstructure of the underlying graph. We also present experimental results analyzing issues in load balancing related to our algorithms.

    Original languageEnglish (US)
    Pages (from-to)357-370
    Number of pages14
    JournalJournal of Computer and System Sciences
    Issue number3
    StatePublished - 1996

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Networks and Communications
    • Computational Theory and Mathematics
    • Applied Mathematics


    Dive into the research topics of 'Dynamic load balancing by random matchings'. Together they form a unique fingerprint.

    Cite this