Please use this identifier to cite or link to this item:
Title: On the design of fault-tolerant scheduling strategies using primary-backup approach for computational grids with low replication costs
Authors: Zheng, Q.
Veeravalli, B. 
Tham, C.-K. 
Keywords: Directed acyclic graphs
Grid computing
Independent tasks
Issue Date: 2009
Citation: Zheng, Q., Veeravalli, B., Tham, C.-K. (2009). On the design of fault-tolerant scheduling strategies using primary-backup approach for computational grids with low replication costs. IEEE Transactions on Computers 58 (3) : 380-393. ScholarBank@NUS Repository.
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.
Source Title: IEEE Transactions on Computers
ISSN: 00189340
DOI: 10.1109/TC.2008.172
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Aug 2, 2021


checked on Jul 26, 2021

Page view(s)

checked on Aug 3, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.