Taxonomy of dynamic task scheduling schemes in distributed computing systems

System state estimation and decision making are the two major components of dynamic task scheduling in a distributed computing system. Combinations of solutions to each individual component constitute solutions to the dynamic task scheduling problem. It is important to consider a solution to the state estimation problem separate from a solution to the decision making problem to understand the similarities and differences between different solutions to dynamic task scheduling. Also, a solution to the state estimation problem has a significant impact on the scalability of a task scheduling solution in large scale distributed systems. The author presents a taxonomy of dynamic task scheduling schemes that is synthesised by treating state estimation and decision making as orthogonal problems. Solutions to estimation and decision making are analysed in detail and the resulting solution space of dynamic task scheduling is clearly shown. The proposed taxonomy is regular, easily understood, compact, and its wide applicability is demonstrated by means of examples that encompass solutions proposed in the literature. The taxonomy illustrates possible solutions that have not been evaluated and those solutions that may have potential in future research