Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract)
Bhaskar Ghosh, Subramanian Muthukrishnan · 1994
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.