Effect of network latency on load sharing in distributed systems

Distributed computing systems consist of computers interconnected by communications links. In such systems, Load sharing is an important technique used to improve system performance in which jobs are transferred from overloaded nodes to underloaded ones. However, due to the ubiquitous and inescapable presence of network latencies, various pitfalls arise which can adversely affect the beneficial effects of job transfer. In this paper, we present an investigation into the effect of network latency on load sharing. The notions of Transfer Pair, and Load-Sharing Window are rigorously defined. A general expression for the probability distribution function of the Load-Sharing Window is derived. A class of rules, called quantile rules, is introduced and their role in avoiding unproductive job redistribution in spite of network latency, as well as to make multiple job transfers, is explained. The general technique is applied to the specific case of a distributed computing system consisting of M/M/1 queues. For this case, an expression for the mean of the Load-Sharing Window is derived. Numerical computations are presented, and their significance discussed.