Hydrodynamic load balancing

This paper presents a hydrodynamic framework to solving the dynamic load balancing problem in heterogeneous distributed systems. In this approach, each processor is viewed as a liquid cylinder where the cross-sectional area corresponds to the capacity of the processor, the communication links are modeled as liquid channels between the cylinders, the workload is represented by liquid, and the load balancing algorithm manages the flow of the liquid. It is proven that all algorithms under this framework converge geometrically to the state of equilibrium, in which the heights of the liquid columns are the same in all the cylinders. In this way, each processor obtains an amount of workload proportional to its capacity. A hydrodynamic algorithm is presented and its performance is evaluated. The algorithm is applied to solve several practical applications to demonstrate the applicability of the framework