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