Reducing communication overhead in a dynamic load sharing algorithm

• Main Author: Baraka, Rebhi S.
• Format: text
• Language: English
• Published: Animo Repository 1996
• Subjects: Algorithms; Dymanic programming; Electronic data processing > Distributed processing; Programming (Electronic computers); Information theory; Communication; Computer Sciences
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1718
• Institution: De La Salle University

Little research has been performed to reduce communication overhead, associated with load state information collection, in dynamic load sharing for distributed systems. This is due to the assumption that such overhead can be considered negligible compared to the overhead associated with the transfer of work load [CABR86, MIRC89]. However, this communication overhead is considered to be a major disadvantage of dynamic load sharing [SHIR95]. It may negate the benefits of load sharing and degrade system performance [EAGE86, JUAN86, QIAN94]. Thus, a better dynamic load sharing algorithm must reduce the communication overhead caused by information collection [XU93]. A new load sharing algorithm with reduced communication overhead is presented. It is based on a general approach and a model of distributed control for the coordination among cooperating processes with minimum communication overhead. The approach, as employed by the algorithm, is to replicate (disseminate) the load information of a node to other nodes, to relax the copy consistency constraints resulting from the replication, and to make each node treat the information it has about other nodes, which may be outdated due to unpredictable communication delays, as an estimate of the global state, and hence use it for load sharing decisions. The algorithm incurs less communication overhead than an algorithm based on the bidding approach. The algorithm is distributed, dynamic, nonpreemptive, and cooperative.