In most current locally distributed systems, the work generated at a node is processed there; little sharing of computational resources is provided. In such systems it is possible for some nodes to be heavily loaded while others are lightly loaded, resulting in poor overall system performance. The purpose of load sharing is to improve performance by redistributing the workload among the nodes.
The load sharing policies with the greatest potential benefit are adaptive in the sense that they react to changes in the system state. Adaptive policies can range from simple to complex in their acquisition and use of system state information . The potential advantage of a complex policy is the possibility that such a scheme can take full advantage of the processing power of the sytem. The potential disadvantages are the overhead cost, and the possibility that a highly tuned policy will behave in an unpredictable manner in the face of the inaccurate information with which it inevitably will be confronted.
The goal of this paper is not to propose a specific load sharing policy for implementation, but rather to address the more fundamental question of the appropriate level of complexity for load sharing policies. We show that extremely simple adaptive load sharing policies, which collect very small amounts of system state information and which use this information in very simple ways, yield performance close to that expected from more complex policies whose viability is questionable. We conclude that simple policies offer the greatest promise in practice because of their combination of nearly optimal performance and inherent stability.