Back to Search
Start Over
Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms.
- Source :
- Journal of Scheduling; Oct2012, Vol. 15 Issue 5, p615-627, 13p
- Publication Year :
- 2012
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
PROBABILITY theory
COMPUTATIONAL complexity
BLOCK diagrams
ACYCLIC model
Subjects
Details
- Language :
- English
- ISSN :
- 10946136
- Volume :
- 15
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Journal of Scheduling
- Publication Type :
- Academic Journal
- Accession number :
- 79469549
- Full Text :
- https://doi.org/10.1007/s10951-011-0236-y