OPTIMAL TIME-VARYING LOAD SHARING FOR DIVISIBLE LOADS

A load sharing problem involving the optimal load allocation of divisi ble loads in a distributed computing system consisting of N processors interconnected through a bus-oriented network is investigated, For a divisible load, the workload is infinitely divisible so that each frac tion of the workload can be distributed and independently computed on each processor. For the first time in divisible load theory, an analys is is provided in the case when the processor speed and the channel sp eed are time varying due to background jobs submitted to the distribut ed system with nonnegligible communication delays. A numerical method to calculate the average of the time-varying processor speed and the c hannel speed and an algorithm to find the optimal allocation of the wo rkload to minimize the total processing finish time are proposed via a deterministic analysis. A stochastic analysis which makes use of Mark ovian queueing theory is introduced for the case when arrival and depa rture times of the background jobs are not known.