📖
Fault-tolerance Strategies for Linear Chains of Moldable Tasks
Li Han, Yves Robert, Frédéric Vivien

Fault-tolerance Strategies for Linear Chains of Moldable Tasks

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Fault-tolerance Strategies for Linear Chains of Moldable Tasks
Author / Organization Li Han, Yves Robert, Frédéric Vivien
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2026
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-255367
Original Source Link Visit Source Page on hal.science »