Scheduling in distributed computing systems
Thomas L. Casavant · 1986
This thesis addresses the problem of behavior characterization for a class of computations known as distributed scheduling algorithms. A formal model of this type of computation is proposed which allows the consistent specification of performance and efficiency attributes of algorthms independent of a particular implementation. This form of analysis is necessary if there is to be a basis of quantitative comparison between alternative solutions to a scheduling problem in a distributed environment. In addition, the isolation of cause and effect with respect to the tuning of resource management facilities such as scheduling algorithms is paramount to the favorable performance of a distributed computing system in general. To date, no such mechanism or method of analysis exists. A taxonomy and extensive classification and survey of the current literature is also presented in order to provide a basis for qualitative comparison between approaches. The results of this thesis indicate that differing approaches to the problem provide different levels of performance and efficiency, and that utilizing the formal model presented here, intelligent design choices may be made prior to system prototyping or ad hoc simulation. A quantitative study of three examples which cover a spectrum of differing amounts of global knowledge requirements is presented, and general characteristics of distributed scheduling performance are proposed and investigated. The model is also applicable to a larger class of applications defined as distributed decision-making, and the generalization of the model in this manner is discussed.