Fault-tolerance Strategies for Linear Chains of Moldable Tasks

This work considers fault-tolerant strategies to protect linear chains of moldable tasks from fail-stop errors, or from silent errors, or from both. To the best of our knowledge, the study of linear chains of moldable tasks on error-prone platforms has never been tackled, despite the importance and ubiquitousness of moldable tasks in scientific and real-time applications. On the contrary, several studies are available in the literature for linear chains of sequential or rigid parallel tasks. Extending these studies to moldable tasks is challenging; in addition to changing the execution time, the number of processors chosen for each task also changes the probability of an error striking that task. For fail-stop errors, resilience is achieved via checkpoints taken after some well-chosen tasks. For silent errors (and when dealing with both error types), checkpoints are preceded by a verification mechanism, and are taken only if no silent error has been detected by the verification. We also investigate a variant which is commonly used for real-time tasks, and where each task is augmented by its own verification mechanism. For all scenarios, the optimization problem is to decide how many processors to assign to each task and where to place (verified) checkpoints in order to minimize the expectation of the total execution time. For each scenario, either we provide an optimal algorithm or we prove the NP-completeness of the problem, thereby laying complete theoretical foundations for the problem. Finally, we discuss the limitations and possible extensions of this work.