Please use this identifier to cite or link to this item: https://doi.org/10.1109/TC.2008.172
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
Fault-tolerance
Grid computing
Independent tasks
Primary-backup
Issue Date: 2009
Source: 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. https://doi.org/10.1109/TC.2008.172
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
URI: http://scholarbank.nus.edu.sg/handle/10635/56890
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.

SCOPUSTM   
Citations

42
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

24
checked on Dec 5, 2017

Page view(s)

26
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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