J Grid Computing (2009) manuscript No. (will be inserted by the editor) Grid Resource Availability Prediction-Based Scheduling and Task Replication

Abstract 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 im-prove 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. Sev-eral prediction techniques then forecast resource tran-sitions into the model’s states. We analyze the accu-racy of our predictors, which outperform existing ap-proaches. We also propose and study several classes of schedulers that utilize the predictions, and a method for combining scheduling factors. We characterize the inherent tradeoff between job makespan and the num-ber of evictions due to failure, and demonstrate how our schedulers can navigate this tradeoff under various scenarios. Lastly, we propose job replication techniques, which our schedulers utilize to replicate those jobs that are most likely to fail. Our replication strategies outper-form others, as measured by improved makespan and fewer redundant operations. In particular, we define