On the design of fault-tolerant scheduling strategies using primary-backup approach for computational grids with low replication costs

Abstract

Fault-tolerant scheduling is an imperative step for large-scale computational Grid systems, as often geographically distributed nodes cooperate to execute a task. By and large, primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary copy and a backup copy on two different processors. For independent tasks, the backup copy can overload with other backup copies on the same processor, as long as their corresponding primary copies are scheduled on different processors. However, for dependent tasks, precedence constraint among tasks must be considered when scheduling backup copies and overloading backups. In this paper, we first identify two cases that may happen when scheduling dependent tasks with primary-backup approach. For one of the cases, we derive two important constraints that must be satisfied. Further, we show that these two constraints play a crucial role in limiting the schedulability and overloading efficiency of backups of dependent tasks. We then propose two strategies to improve schedulability and overloading efficiency, respectively. We propose two algorithms, called the Minimum Replication Cost with Early Completion Time (MRC-ECT) algorithm and the Minimum Completion Time with Less Replication Cost (MCT-LRC) algorithm, to schedule backups of independent jobs and dependent jobs, respectively. Algorithm MRC-ECT is shown to guarantee an optimal backup schedule in terms of replication cost for an independent task, while MCT-LRC can schedule a backup of a dependent task with minimum completion time and less replication cost. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms and strategies. © 2009 IEEE.