This paper proposes a new dynamic load-balancing technique for multiprocessors based on the “gradient model.” The algorithm is fully distributed and asynchronous. It appears to be applicable to a wide variety of system topologies. In this paper, the authors present the basic algorithm, illustrate the key ideas with good examples, and evaluate the performance through simulations on several programming problems and interconnection topologies. I found the ideas to be quite interesting--either this algorithm or some variant of it could be successful in a production environment. The writing style was also commendable; the paper is readable with minimal effort.

The load-balancing algorithm compares the workload at each processor with that of its immediate neighbors; excess work moves toward lightly loaded processors. This scheme does depend on the assumption that work can travel arbitrarily far without altering the meaning of the program. The authors implemented their algorithm in the simulator for “Rediflow,” a loosely coupled applicative language-based system that uses demand-based evaluation. However, it appears to me that most of their results are independent of this specific computing model. My only criticism of the paper is that the authors did not compare performance of their scheme with other load-balancing algorithms. It might have helped to put their results in a better context. Overall, I do believe this paper is worth reading.