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.