On the complexity of task graph scheduling with transient and fail-stop failures
BENOIT, Anne
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Voir plus >
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
BENOIT, Anne
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
ROBERT, Yves
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
< Réduire
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]
Langue
en
Document de travail - Pré-publication
Résumé en anglais
This paper deals with the complexity of task graph scheduling 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 ...Lire la suite >
This paper deals with the complexity of task graph scheduling 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. Our main result is that this problem is #P'- Complete (hence at least as hard as NP-Complete problems), with both transient and fails-stop processor failures. We also study the complexity of a restricted class of schedules, where a task cannot be scheduled before all replicas of all its predecessors have completed their execution.< Réduire
Origine
Importé de halUnités de recherche