Treating uncertainty in distributed scheduling

In distributed systems the scheduler of an overloaded node may choose to transfer the execution of one or more tasks to other less busy nodes, in order to minimize their expected service times, or to increase the number of tasks that meet their deadlines, among other criteria. One solution makes use of Bayesian theory to infer the load state of the system and, based on this information, the scheduler of a busy node chooses an "appropriate" node to transfer a task too. The meaning of "appropriate" will be a function of the objectives established in the adopted location policy. In the Bayesian decision method, objectives are represented by a utility function. However, the development of a utility function can be a tricky and somewhat subjective task. In this paper, we describe a new approach that easily maps transfer objectives into useful mathematical expressions, representing location policy objectives by fuzzy sets. The proposed approach was successfully employed to add objectives to a Bayesian decision-based algorithm improving the number of tasks that are executed over time in a distributed real-time system. (C) 2001 Elsevier Science Inc. All rights reserved.