Reducing communication overhead in a dynamic load sharing algorithm

Date of Publication

1996

Document Type

Master's Thesis

Degree Name

Master of Science in Computer Science

Subject Categories

Computer Sciences

College

College of Computer Studies

Department/Unit

Computer Science

Thesis Adviser

Philip Chan

Defense Panel Chair

Dr. Harry Joson

Defense Panel Member

Kelsey Hartigan Go
Mitch Andaya

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Print

Accession Number

TG02499

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

123, [10] leaves; 28 cm.

Keywords

Algorithms; Dymanic programming; Electronic data processing -- Distributed processing; Programming (Electronic computers); Information theory; Communication

This document is currently not available here.

Share

COinS