A distributed load‐balancing policy for a multicomputer

TLDR

The paper addresses load balancing in a multicomputer cluster of independent computers connected by a local area network. It proposes three algorithms—local load monitoring, load‑information exchange, and process migration—to maintain system load balance. The distributed policy is dynamic and stable, with each processor applying the same algorithm to monitor load, exchange information, and migrate processes without prior knowledge of resource requirements. Implementation results demonstrate the feasibility of network‑based distributed systems for uniform access, resource sharing, improved reliability, and the use of workstations lacking secondary storage.

Abstract

Abstract This paper deals with the organization of a distributed load‐balancing policy for a multicomputer system which consists of a cluster of independent computers that are interconnected by a local area communication network. We introduce three algorithms necessary to maintain load balancing in this system: the local load algorithm, used by each processor to monitor its own load; the exchange algorithm, for exchanging load information between the processors, and the process migration algorithm that uses this information to dynamically migrate processes from overloaded to underloaded processors. The policy that we present is distributed, i.e. each processor uses the same policy. It is both dynamic, responding to load changes without using an a priori knowledge of the resources that each process requires; and stable, unnecessary overloading of a processor is minimized. We give the essential details of the implementation of the policy and initial results on its performance. Our results confirm the feasibility of building distributed systems that are based on network communication for uniform access, resource sharing and improved reliability, as well as the use of workstations without a secondary storage device.