Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jpdc.2008.11.007
Title: On the design of communication-aware fault-tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices
Authors: Zheng, Q. 
Veeravalli, B. 
Keywords: Communication delay
Directed acyclic graphs
Grid computing
Primary-backup
Replication cost
Response time
Issue Date: Mar-2009
Source: Zheng, Q., Veeravalli, B. (2009-03). On the design of communication-aware fault-tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices. Journal of Parallel and Distributed Computing 69 (3) : 282-294. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jpdc.2008.11.007
Abstract: Fault-tolerant scheduling is an imperative step for large-scale computational Grid systems, as often geographically distributed nodes co-operate to execute a task. By and large, primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary and a backup on two different processors. In this paper, we address the problem of how to schedule DAGs in Grids with communication delays so that service failures can be avoided in the presence of processors faults. The challenge is, that as tasks in a DAG have dependence on each other, a task must be scheduled to make sure that it will succeed when any of its predecessors fails due to a processor failure. We first propose a communication model and determine when communications between a backup and backups of its successors are necessary. Then we determine when a backup can start and its eligible processors so as to guarantee that every DAG can complete upon any processor failure. We develop two algorithms to schedule backups, which minimize response time and replication cost, respectively. We also develop a suboptimal algorithm which targets minimizing replication cost while not affecting response time. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms. © 2008 Elsevier Inc. All rights reserved.
Source Title: Journal of Parallel and Distributed Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/56888
ISSN: 07437315
DOI: 10.1016/j.jpdc.2008.11.007
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

15
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

9
checked on Dec 5, 2017

Page view(s)

20
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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