Review: Hydrodynamic Load Balancing

Following the discussion on the need for a scalable distributed landmarking algorithm, I came across these two papers. These are not directly related to landmarking problem, but address the problem of distributed load balancing with a potential energy based approach. Even though their potential energy comes from hydrodynamic point of view, I wonder whether that can be twisted into my spring system.

• C. Hui and S.T. Chanson, "Hydrodynamic Load Balancing", IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 11, Nov. 1999
• C. Hui and S.T. Chanson, "A Hydro-dynamic Approach to Heterogeneous Dynamic Load Balancing in a Network of Computers", In Proceedings of the International Conference on Parallel Processing, 1996

The first paper goes deep into the theory behind the proposed mechanism proving the convergence and accuracy of the algorithm. The other paper describes the algorithm as it to be implemented in the system.

In the hydrodynamic approach, the network is considered as graph of V nodes and E edges. Each node is assumed to have a water cylinder and the load in a node is represented by the liquid contained in the cylinder; The cross section of the cylinder is represented by the capacity of the node. Each edge in E is assumed to be a liquid channel connecting the cylinders at the end nodes. The paper proves that the load sharing becomes fair when the global potential energy presented by the liquid columns is minimized, in another words, when the heights of the liquid columns are same in all cylinders. The papers provides a systematic way of transfer of liquids between cylinders that leads to this equilibrium condition. And it is proven that this convergence will occur within a finite period of time.

There are two issues regarding applying the same theory in my work:

1. The potential energy in the hydrodynamic system is stored in the cylinder, i.e. in the nodes of the graph whereas in the spring system, the energy is stored in the springs, i.e. in the edges. Further, we don't have the "equal liquid column height when equilibirium" type of phenomena in a spring system; i.e. we can't claim at minimum potential energy all the spring will have same stretch factor, same force, or anything (or I couldn't think about any).
2. The distributed load balancing mechanism is more concerned about devising a distribute scheme that reacts to the load changes dynamically than producing an algorithm that produce less message overhead.

So still the distributed landmarking problem remains open.