This talk presents a dynamic load balancing algorithm for a network of heterogeneous computers. Our approach is based on a fast distributed precomputation step calculating the necessary load movements. When dealing with slow network connections or incomplete load information often a perfect balanced load is not necessary, therefore the allowed degree of inbalance is adjustable.

A detailed average case analysis is carried out concerning the total load transfer and the number of transfer rounds. Its performance is empirically demonstrated solving the satisfiability problem on a heterogeneous network of workstations.

Return to the LSDO tutorial topics page