Dynamic Load Balancing by Random Matchings

Abstract

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.