Static load balancing occurs when the decision to transfer a computation is independent of system state. This paper models static load balancing for a heterogeneous distributed system, assuming each computation is completed at a single node, and assuming communications delay depends only on total traffic in the network. The model is formulated as a nonlinear optimization problem using Lagrange multipliers. Assumptions to limit the scope of the problem reduce the number of variables from n2 to n.
The triangle inequality asserts that forwarding a message through an intermediate node is always more costly than sending the message directly. Assuming the triangle inequality, the authors show that a distributed system can be partitioned into sources of messages invoking remote computations, sinks of these messages where the computations are performed, and neutrals where all computation is performed locally. The optimal load balancing strategy is achieved by describing an algorithm for obtaining the optimal strategy for a given communication time, and, through a second algorithm, allowing the communication time to be varied. The authors give a numerical example involving an artificial distributed system.
The key assumption of the model is not the triangle inequality; it is, rather, an implicit assumption that the nodes all have the same processing capabilities, and any computation must be processed in its entirety at a fixed, but arbitrary, node. The partition into sources, sinks, and neutrals follows from this assumption.
