Grid resource availability prediction-based scheduling and task replication

The frequent and volatile unavailability of volunteer-based Grid computing resources challenges Grid schedulers to make effective job placements. The manner in which host resources become unavailable will have different effects on different jobs, depending on their runtime and their ability to be checkpointed or replicated. A multi-state availability model can help improve scheduling performance by capturing the various ways a resource may be available or unavailable to the Grid. This paper uses a multi-state model and analyzes a machine availability trace in terms of that model. Several prediction techniques then forecast resource transitions into the model's states. This study analyzes the accuracy of proposed predictors, which outperform existing approaches. Later chapters propose and study several classes of schedulers that utilize the predictions, and a method for combining scheduling factors. Scheduling results characterize the inherent tradeoff between job makespan and the number of evictions due to resource unavailability, and demonstrate how prediction-based schedulers can navigate this tradeoff under various scenarios. Schedulers can use prediction-based job replication techniques to replicate those jobs that are most likely to fail. The proposed prediction-based replication strategies outperform others, as measured by improved makespan and fewer redundant operations. Multi-state availability predictor can provide information that allows distributed schedulers to be more efficient---as measured by a new efficiency metric---than others that blindly replicate all jobs or some static percentage of jobs. PredSim, a simulation-based framework, facilitates the study of these topics.