Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines

In queue-based scheduling systems jobs are executed according to a predefined sequential plan; faults may occur that cause jobs to re-execute thus delaying the whole schedule. It is, therefore, important to be able to determine (in real-time) whether a set of pre-ordered jobs will always meet their deadlines: it al-lows for instance to decide online whether to admit a new urgent job in the queue and still guaranty that the whole schedule remains fault-tolerant, i.e. that the remaining jobs still will not miss their deadlines. Our goal in this work is therefore to efficiently test whether a given set of sequenced jobs can tolerate transient faults. We consider different realistic fault models specifying which fault patterns are allowed and how soon failed jobs can be restarted. For each fault model considered we provide efficient algorithms that, given a set of sequenced jobs, decide on the fea-sibility of all the jobs in the schedule. Our algorithms are exact and run in time linear in the number of jobs and thus can be used to make a real-time decision.