A set of nodes and a set of consumers are given, and to each
consumer there corresponds a subset of the nodes. Each consumer has a demand,
which is a load to be distributed among the nodes corresponding to the
consumer. The load at a node is the sum of the loads placed on the node by all
consumers. The load is balanced if no single consumer can shift some load from
one node to another to reduce the absolute difference between the total loads
at the two nodes. The model provides a setting to study the performance of load
balancing as an allocation strategy in large systems.
¶ The set of possible balanced load vectors is examined for infinite
networks with deterministic or random demands. The balanced load vector is
shown to be unique for rectangular lattice networks, and a method for computing
the load distribution is explored for tree networks. An FKG-type inequality is
proved. The concept of load percolation is introduced and is shown to be
associated with infinite sets of nodes with identical load.