Improved Bounds for Discrete Diffusive Load Balancing

In this paper we consider load balancing in a static and discrete setting where a fixed number of indivisible tasks have to be allocated to processors. We assume uniform tasks but the processors may have different speeds. The load of a processor is the number of tasks assigned to it divided by its speed. We consider diffusion load balancing which works in rounds. In every round the processors are allowed to compare their own load with the load of their neighbors and to balance the load with the neighbors, using their local information only. The question is how many rounds does it take until the whole processor network is balanced, meaning the load discrepancy (difference between maximum load and m/n) is minimized. Our balancing algorithm is deterministic and extends the algorithm studied in [1] from the case of uniform speeds to non-uniform speeds. We use a potential function argument to show that a better load balance can be obtained when the algorithm is allowed to run longer compared to the algorithm of [1].