BENOIT, Anne; CANON, Louis-Claude; JEANNOT, Emmanuel; ROBERT, Yves

doi:10.1007/s10951-011-0236-y

Métadonnées

Licence d’utilisation du document

BENOIT, Anne
Laboratoire de l'Informatique du Parallélisme [LIP]
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]

CANON, Louis-Claude
Algorithms for the Grid [ALGORILLE]

JEANNOT, Emmanuel
Efficient runtime systems for parallel architectures [RUNTIME]

Langue

Article de revue

Ce document a été publié dans

Journal of Scheduling. 2012-10-01, vol. 15, n° 5, p. 615-627

Springer Verlag

Résumé en anglais

This paper deals with the reliability of task graph schedules with transient and fail-stop failures. While computing the reliability of a given schedule is easy in the absence of task replication, the problem becomes much more difficult when task replication is used. We fill a complexity gap of the scheduling literature: our main result is that this reliability problem is #P'-Complete (hence at least as hard as NP-Complete problems), both for transient and for fail-stop processor failures. We also study the evaluation of a restricted class of schedules, where a task cannot be scheduled before all replicas of all its predecessors have completed their execution. Although the complexity in this case with fail-stop failures remains open, we provide an algorithm to estimate the reliability while limiting evaluation costs, and we validate this approach through simulations.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche