On the stability of a distributed dynamic load balancing algorithm

We present a new fully distributed dynamic load balancing algorithm called DASUD (Diffusion Algorithm Searching Unbalanced Domains). Since DASUD is iterative and runs in an asynchronous way, a mathematical model that describes DASUD behaviour has been proposed and has been used to prove DASUD´s convergence. DASUD has been evaluated by comparison with another well known strategy from the literature, namely, the SID (Sender Initiated Diffusion) algorithm. The comparison was carried out by considering a large set of load distributions which were applied to ring, torus and hypercube topologies, and the number of processors ranged from 8 to 128. From these experiments we have observed that DASUD outperforms the SID strategy as it provides the best trade-off between the global balance degree obtained at the final state and the number of iterations required to reach such a state