Afficher la notice abrégée

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

hal.structure.identifierAlgorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorBENOIT, Anne
hal.structure.identifierEfficient runtime systems for parallel architectures [RUNTIME]
dc.contributor.authorCANON, Louis-Claude
hal.structure.identifierEfficient runtime systems for parallel architectures [RUNTIME]
dc.contributor.authorJEANNOT, Emmanuel
hal.structure.identifierAlgorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorROBERT, Yves
dc.date.accessioned2024-04-15T09:49:37Z
dc.date.available2024-04-15T09:49:37Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198272
dc.description.abstractEnThis 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.
dc.language.isoen
dc.title.enOn the complexity of task graph scheduling with transient and fail-stop failures
dc.typeDocument de travail - Pré-publication
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-00457511
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00457511v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=BENOIT,%20Anne&CANON,%20Louis-Claude&JEANNOT,%20Emmanuel&ROBERT,%20Yves&rft.genre=preprint


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée