Scheduling computational workflows on failure-prone platforms

We study the scheduling of computational workflows on compute resources thatexperience exponentially distributed failures. When a failure occurs, rollback and recovery is usedto resume the execution from the last checkpointed state. The scheduling problem is to minimizethe expected execution time by deciding in which order to execute the tasks in the workflow andwhether to checkpoint or not checkpoint a task after it completes. We give a polynomial-timealgorithm for fork graphs and show that the problem is NP-complete with join graphs. Our mainresult is a polynomial-time algorithm to compute the execution time of a workflow with specifiedto-be-checkpointed tasks. Using this algorithm as a basis, we propose efficient heuristics for solvingthe scheduling problem. We evaluate these heuristics for representative workflow configurations.Nous étudions l'ordonnancement de flux de calculs sur des machines sujettes à des pannesqui suivent une loi exponentielle. Quand une faute arrive, la plateforme récupère son état lorsdu dernier point de sauvegarde de données. Le problème est ici de minimiser l'espérance dutemps total d'exécution en choisissant l'ordre d'exécution des tâches ainsi que les tâches dont la sortie est sauvegardée (checkpoint). Nous proposons un algorithme polynomial pour les forkainsi qu'une preuve de NP-complétude pour les joins. Le résultat principal de ce travail est unalgorithme polynomial pour évaluer le temps d'exécution d'un DAG ordonnancé. Cet algorithme permet l'évaluation d'heuristiques pour résoudre le problème d'ordonnancement, nous en proposons et les évaluons sur des flux de calculs représentatifs de configurations actuelles