STABLE DISTRIBUTED SCHEDULING ALGORITHM.

A new scheduling algorithm is described for a multicomputer connected in a point-to-point fashion. The algorithm is both distributed (every processor runs the same algorithm) and stable (collective load balancing decisions will not cause unnecessary overloading of a processor in the network). It is assumed that process execution times are not known in advance and that inter-processor transfer times are non-trivial. Load is balanced by migrating suitable jobs after they have been run long enough to obtain an estimate of their required service time. The algorithm is suitable for job scheduling in a distributed time-sharing system implemented on a multicomputer. Performance of the algorithm is investigated through simulation.