TR-95-25: The Effect of Scheduling Discipline on Sender-Initiated and Receiver-Initiated Adaptive Load Sharing in Homogeneous Distributed Systems

Load sharing is a technique to improve the performance of distributed systems by distributing the system workload from heavily loaded nodes to lightly loaded nodes in the system. Previous studies have considered two adaptive load sharing policies: sender-initiated and receiver-initiated. In the sender-initiated policy, a heavily loaded node attempts to transfer work to a lightly loaded node and in the receiver-initiated policy a lightly loaded node attempts to get work from a heavily loaded node. Most of the previous studies have assumed the first-come/first-served (FCFS) node scheduling policy; furthermore, analyses and simulations in these studies have been done under the assumption that the job service times are exponentially distributed and the job arrivals form a Poisson process. The goal of this paper is to fill the void in the existing literature. We study the impact of these assumptions on the performance of the sender-initiated and receiverinitiated policies. We consider three node scheduling policies – first-come/first-served (FCFS), shortest job first (SJF), and round robin (RR) policies.