A Fault-Tolerant Workflow Scheduling Algorithm for Grid with Near-Optimal Redundancy

摘要

In scheduling workflows in grid environment, concerns such as minimizing the makespan and cost, meeting the time and budget constraints and the possibility of resource failures and so on have motivated researchers to propose numerous scheduling algorithms. Several heuristics and meta-heuristic algorithms have been proposed to address these issues, each of which often only considers one or a few of these criteria. However, less attention has been paid to fault-tolerant scheduling of workflows. Adding fault-tolerance to a workflow scheduling algorithm leads to an inevitable increase in the makespan and cost. Using the resubmission technique may result to an unacceptable increase in the execution time and possible violation of deadline while the replication method increases the execution cost. In this paper, we propose a fault-tolerant workflow scheduling algorithm with near-optimal time and cost overhead. The proposed approach brings a two-fold novelty. First, we assume a stochastic model of workflow with nondeterministic task parameters and use interval arithmetic to model task execution times and propose a new scheduling algorithm in which the task assignment decisions are taken according to the performability fluctuations of the computational resources. Second, we employ an Efficient combination of resubmission and replication techniques to achieve the benefits of both and propose an algorithm for reliable scheduling of scientific workflows with near-optimal additional time and cost. The proposed method, achieves a significant increase in the reliability while the additional execution time and cost is almost negligible.