On the complexity of scheduling checkpoints for computational workflows - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

On the complexity of scheduling checkpoints for computational workflows

Résumé

This paper deals with the complexity of scheduling computational workflows in the presence of Exponential failures. When such a failure occurs, rollback and recovery is used so that the execution can resume from the last checkpointed state. The goal is to minimize the expected execution time, and we have to decide in which order to execute the tasks, and whether to checkpoint or not after the completion of each given task. We show that this scheduling problem is strongly NP-complete, and propose a (polynomial-time) dynamic programming algorithm for the case where the application graph is a linear chain. These results lay the theoretical foundations of the problem, and constitute a prerequisite before discussing scheduling strategies for arbitrary DAGS of moldable tasks subject to general failure distributions.
Fichier principal
Vignette du fichier
RR-7907.pdf (786.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00680386 , version 1 (19-03-2012)

Identifiants

  • HAL Id : hal-00680386 , version 1

Citer

Yves Robert, Frédéric Vivien, Dounia Zaidouni. On the complexity of scheduling checkpoints for computational workflows. [Research Report] RR-7907, INRIA. 2012. ⟨hal-00680386⟩
115 Consultations
189 Téléchargements

Partager

Gmail Facebook X LinkedIn More