Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms
| hal.structure.identifier | Laboratoire de l'Informatique du Parallélisme [LIP] | |
| hal.structure.identifier | Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA] | |
| dc.contributor.author | BENOIT, Anne | |
| hal.structure.identifier | Algorithms for the Grid [ALGORILLE] | |
| dc.contributor.author | CANON, Louis-Claude | |
| hal.structure.identifier | Efficient runtime systems for parallel architectures [RUNTIME] | |
| dc.contributor.author | JEANNOT, Emmanuel | |
| hal.structure.identifier | Laboratoire de l'Informatique du Parallélisme [LIP] | |
| hal.structure.identifier | Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA] | |
| dc.contributor.author | ROBERT, Yves | |
| dc.date.accessioned | 2024-04-15T09:46:01Z | |
| dc.date.available | 2024-04-15T09:46:01Z | |
| dc.date.issued | 2012-10-01 | |
| dc.identifier.issn | 1094-6136 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197971 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Springer Verlag | |
| dc.title.en | Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1007/s10951-011-0236-y | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.journal | Journal of Scheduling | |
| bordeaux.page | 615-627 | |
| bordeaux.volume | 15 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 5 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00653477 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00653477v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Journal%20of%20Scheduling&rft.date=2012-10-01&rft.volume=15&rft.issue=5&rft.spage=615-627&rft.epage=615-627&rft.eissn=1094-6136&rft.issn=1094-6136&rft.au=BENOIT,%20Anne&CANON,%20Louis-Claude&JEANNOT,%20Emmanuel&ROBERT,%20Yves&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||