Implementation of a distributed algorithm for the balancing of integer indivisible loads in distributed systems.

Abstract

One of the important tools within the distributed computer systems is load balancing. The load balancing is a process of redistribution of tasks among multiple processors. This redistribution should be made so that each processor has approximately equal work to do. In this thesis we present a dynamic algorithm for balancing indivisible loads on a network. Our aim is to reach an equilibrium state of the network using a final number of steps. The algorithm works as follows: cach node in the network communicate with its neighbors and balance their loads locally to reach the equilibrium state. The results of the experiments of various load balancing methods, considering two typical load balancing environement centralized and decentralized, indicate that the proposed greedy sort method has more advancements over the others, especially in decentralized than a centralized environement. Key words: Load balancing, indivisible loads, dynamic load balancing.