Methodical analysis of adaptive load sharing algorithms

A method for qualitative and quantitative analysis of load sharing algorithms is presented, using a number of well known examples as illustration. Algorithm design choice are considered with respect to the main activities of information dissemination and allocation decision making. It is argued that nodes must be capable of making local decisions, and for this efficient state, dissemination techniques are necessary. Activities related to remote execution should be bounded and restricted to a small proportion of the activity of the system. The quantitative analysis provides both performance and efficiency measures, including consideration of the load and delay characteristics of the environment. To assess stability, which is also a precondition for scalability, the authors introduce and measure the load-sharing hit-ratio, the ratio of remote execution requests concluded successfully. Using their analysis method, they are able to suggest improvements to some published algorithms