Algorithms for the Correct Implementation of Scheduling Policies in DistributedSystems

摘要

One of the main objectives of distributed systems is improvement of performance. An important way to achieve this is to move waiting jobs from busy to idle processors, or more generally, from heavily loaded to lightly loaded processors. A variety of distributed scheduling policies, amongst which generalizations of centralized policies, e.g., global First Come First Served (FCFS), and truly distributed policies such as Join Shortest Queue (JSQ), has been proposed, and analyzed from a queueing theoretic perspective. Relatively little attention has been paid to distributed algorithms implementing these policies correctly. In the paper the author presents an algorithm for global FCFS, prove its correctness, and obtain its message complexity. The author then shows that the basic mechanisms needed to implement FCFS suffice, with minor changes, for a range of other sender-initiated policies, such as JSQ, as well. (Copyright (c) 1990 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands.)