Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract)

Abstract

The fundamental problems in dynamic load balancing and job scheduling in parallel and distributed computers involve moving load between processors. In this paper, we consider a new model for load movement in synchronous parallel and distributed machines. In each step of our model, each processor can transfer load to at most one neighbor; also, any amount of load can be moved along a communication link between two processors in one step. This is a reasonable model for load movement in significant classes of dynamic load balancing problems.