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

Metadatos

Licencia de uso del documento

BENOIT, Anne
Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
Laboratoire de l'Informatique du Parallélisme [LIP]

CANON, Louis-Claude
Efficient runtime systems for parallel architectures [RUNTIME]

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

Idioma

Document de travail - Pré-publication

Resumen en inglés

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 difﬁcult 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.< Leer menos

Metadatos

Compartir este ítem

Licencia de uso del documento

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

Idioma

Resumen en inglés

URI

Orígen

Centros de investigación