On the complexity of task graph scheduling with transient and fail-stop failures

Anne Benoit (1, 2) , Louis-Claude Canon (3) , Emmanuel Jeannot (3) , Yves Robert (1, 2)

1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
2 LIP - Laboratoire de l'Informatique du Parallélisme
3 RUNTIME - Efficient runtime systems for parallel architectures

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.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Anne Benoit, Louis-Claude Canon, Emmanuel Jeannot, Yves Robert. On the complexity of task graph scheduling with transient and fail-stop failures. 2010. ⟨hal-00457511⟩