Search

Here, we propose a fault-tolerant workflow scheduling algorithm that combines basic redundancies to reduce execution time through minimizing the redundancy overhead. We propose a graph-theory-based divide and conquer approach for selecting fault-tolerance strategies for workflow tasks. The appropriate strategy for each task is determined with respect to runtime situation and the position of the task in the graph. The main idea of the proposed algorithm is that resources are apportioned among concurrently executing tasks such that more replicas are assigned to tasks that benefit more from having extra replicas. We use the concept of concurrency graph for finding idle durations of resources which are used for processing additional task replicas. We also propose an opportunistic method for executing extra replicas of tasks in situations that some resources become idle. Furthermore, we propose a new mapping order scheme for ordering task replicas on resources. The proposed approach achieves a significant performance improvement over the existing approaches especially in situations where few resources are enrolled with the aim of cost reduction. [ABSTRACT FROM AUTHOR]

We herein propose a heuristic redundancy selection algorithm that combines resubmission, replication, and checkpointing redundancies to reduce the resiliency overhead in fault‐tolerant workflow scheduling. The appropriate combination of these redundancies for workflow tasks is obtained in two consecutive phases. First, to compute the replication vector (number of task replicas), we apportion the set of provisioned resources among concurrently executing tasks according to their needs. Subsequently, we obtain the optimal checkpointing interval for each task as a function of the number of replicas and characteristics of tasks and computational environment. We formulate the problem of obtaining the optimal checkpointing interval for replicated tasks in situations where checkpoint files can be exchanged among computational resources. The results of our simulation experiments, on both randomly generated workflow graphs and real‐world applications, demonstrated that both the proposed replication vector computation algorithm and the proposed checkpointing scheme reduced the resiliency overhead. [ABSTRACT FROM AUTHOR]