Please use this identifier to cite or link to this item:
|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.
Directed acyclic graphs
|Issue Date:||Mar-2009||Citation:||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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.