Tolerance to Multiple Transient Faults for Aperiodic Tasks in Hard Real-Time Systems.
AbstractReal-time systems are being increasingly used in several applications which are time-critical in nature. Fault tolerance is an essential requirement of such systems, due to the catastrophic consequences of not tolerating faults. In this paper, we study a scheme that guarantees the timely recovery from multiple faults within hard real-time constraints in uniprocessor systems. Assuming earliest-deadline-first scheduling (EDF) for aperiodic preemptive tasks, we develop a necessary and sufficient feasibility-check algorithm for fault-tolerant scheduling with complexity $O(n^2 \cdot k)$, where $n$ is the number of tasks to be scheduled and $k$ is the maximum number of faults to be tolerated.
Introduction
The interest in embedded systems has been growing steadily in the recent past, specially those
ples include autopilot systems, satellite and launch vehicle control, as well as robots, whether in
collaborating teams or not. For some of these systems, termed hard real-time systems (HRTSs), the
consequences of missing a deadline may be catastrophic. The ability to tolerate faults in HRTSs is
crucial, since a task can potentially miss a deadline when faults occur. In case of a fault, a deadline
can be missed if the time taken for recovery from faults is not taken into account during the phase
that tasks are submitted/accepted to the system. Clearly, accounting for recovery from faults is an
essential requirement of HRTSs.
When dealing with such HRTSs, permanent faults can be tolerated by using hot-standby spares
[KS86], or they can be masked by modular redundancy techniques [Pra86]. In addition to permanent
faults, tolerance to transient faults is very important, since it has been shown to occur much more
frequently than permanent faults [IR86, IRH86, CMS82]. In a study, an orbiting satellite containing
a microelectronics test system was used to measure error rates in various semiconductor devices
including microprocessor systems [CMR92]. The number of errors, caused by protons and cosmic
ray ions, mostly ranged between 1 and 15 in 15-minute intervals, and was measured to be as high
as 35 in such intervals. More examples of such safety critical applications can be found in [LH94].
Transient faults can be dealt with through temporal redundancy, that is, allowing extra time (slack)
in the schedule to re-execute the task or to execute a recovery block [HLMSR74].
The problem solved in this paper is as follows. Given a set of n aperiodic tasks,
we seek to determine if each task in the set T is able to complete execution before its deadline
under EDF scheduling even if the system has to recover from (at most) k faults. We consider a
uniprocessor system and assume that each task may be subjected to multiple transient faults.
A simple solution would be to check the feasibility of each of the schedules generated by the
possible combination of faults using the approach described in [LLMM99] for each schedule.
The high complexity of this scheme provides the impetus for searching for a more efficient solution.
The solution presented in this paper develops an optimal (necessary and sufficient) feasibility check
that runs in O(n 2 \Delta time in the worst case.
Although we consider aperiodic tasks, we note that the technique presented in this paper can be
used to verify the fault-tolerance capabilities of a set of periodic tasks by considering each instance
of a periodic task as an aperiodic task within the Least Common Multiple of the periods of all the
periodic tasks. Moreover, scheduling aperiodic tasks is the basis for scheduling periodic tasks in
frame-based systems, where a set of tasks (usually having precedence constraints) is invoked at regular
time intervals. This type of systems is commonly used in practice because of its simplicity. For
example, in tracking/collision avoidance applications, motion detection, recognition/verification,
trajectory estimation and computation of time to contact are usually component sub-tasks within
a given frame (period) [CBM93]. Similarly, a real-time image magnification task might go through
the steps of non-linear image interpolation, contrast enhancement, noise suppression and image
extrapolation during each period [NC96]. Even though these are periodic tasks, the system period
is unique and therefore the scheduling of the each instance (corresponding in our nomenclature to
an "aperiodic" task) can be done within a specific time interval.
The rest of this paper is organized as follows. In Section 2 we present the model and notation
for the aperiodic, fault-tolerant scheduling problem. In Section 3 we introduce an auxiliary function
that will aid in the presentation of our solution. In Section 4 we describe the feasibility tests for
a set of tasks under a specific fault pattern and generalize it in Section 5 for any fault pattern,
examining the worst case behavior with respect to k faults. In Section 6, we survey some related
work and, in Section 7, we finalize the paper with concluding remarks and directions for future
work.
Model and Notation
We consider a uniprocessor system, to which we submit a set T of n tasks: g. A
task - i is modeled by a tuple - is the ready time (earliest start time of
the task), D i is the deadline, and C i is the maximum computation time (also called worst case
execution time). The set of tasks that become ready at a given time t is denoted by RS(T ; t).
That is, RS(T
We assume EDF schedules with ties in deadlines broken arbitrarily. The schedule of T is
described by the function
" if EDF does not schedule any task between t and t
time. We will use EDF (T ) to refer to the EDF schedule of T .
We define e i to be the time at which task - i completes execution in EDF (T ), and we define the
function to be the number of free slots between
is, the number of slots for which EDF (T ; (excluding the slot that starts at t 2 ). EDF (T ) is
said to be feasible if e i - D i for all
It is assumed that faults can be detected at the end of the execution of each task. The time
required by the fault detection mechanism can be added to the worst case computation time C i of
the task and does not hinder the timeliness of the system. Many mechanisms have been proposed
for fault detection at the user level, the operating system level, and the hardware level. At the user
level, a common technique is to use consistency or sanity checks, which are procedures supplied
by the user, to verify the correctness of the results [HA84, YF92]. For example, using checksums,
checking the range of the results or substituting a result back into the original equations can be
used to detect a transient error.
Many mechanisms that exist in operating systems and computer hardware may be used for
error detection and for triggering recovery. Examples are the detection of illegal opcode (caused by
bus error or memory corruption), memory range violation, arithmetic exceptions and various time-out
mechanisms. Hardware duplication of resources can also be used for detecting faults through
comparison of results. It should be noted, however, that while each of the mechanisms described
above is designed for detecting specific types of faults, it has been long recognized that it is not
possible for a fault detection mechanism to accomplish a perfect coverage over arbitrary types of
faults.
When a fault is detected, the system enters a recovery mode where some recovery action must be
performed before the task's deadline. We assume that a task - i recovers from a fault by executing
a recovery block [HLMSR74, LC88], - i;1 at the same priority of - i . A fault that occurs during the
execution of - i;1 is detected at the end of - i;1 and is recovered from by invoking a second recovery
block, - i;2 , and so on. It is assumed that the maximum time for a recovery block of - i to execute
is . The recovery blocks for each task may have a different execution time from the task itself;
in other words, the recovery is not restricted to re-execution of the task. Recovery blocks can be
used for avoiding common design bugs in code, for providing a less accurate result in view of the
limited time available for recovery, or for loading a "safe" state onto memory from some stable
source (across the network or from shielded memory).
We shall denote a pattern of faults over T as a set g, such that f i is the number
of times the task - i 2 T or its recovery blocks will fail before successful completion. We use
to denote the EDF schedule of T under the fault pattern F , that is, when - i is forced
to execute f i recovery blocks. EDF F (T ) is said to be feasible if for all its
recovery blocks complete by D i . Note that EDF F (T ) cannot be feasible if
for any i.
Given a task set T and a specific fault pattern F , we define two functions. The first function,
defines the amount of work (execution time) that remains to be completed at time t in
EDF (T ). This work is generated by the tasks that became ready at or before time t, that is by
the tasks in f- Specifically,
where the -
\Gamma operator is defined as a -
At a time t, any positive amount of work
in W decreases by one during the period between t, while when a task becomes
ready at t, the work increases by the computation time of this task.
The second function, W F (T ; t) is defined in a similar way, except that we include time for
the recovery of failed tasks at the point they would have completed in the fault-free schedule.
Specifically,
The two functions defined above will be used to reason about the extra work needed to recover
from faults. Note that although task - i may complete at a time different than e i in EDF F (T ), the
function W F has the important property that it is equal to zero only at the beginning of an idle
time slot in EDF F (T ). This, and other properties of the two functions defined above are given
next.
only if
there is no work to be done at time t in EDF (T ), which means that any task with R i - t finishes
at or before time t in the fault-free case.
Property 2: W F only if there is no work to be done at time t in EDF F (T ),
which means that any task with R i - t finishes at or before time t when the tasks are subject to
the fault pattern F .
Property 3: W F That is, the amount of work incurred when faults are
present is never smaller than the amount of work in the fault-free case.
That is, the slot before the end of a task is never idle.
The above four properties follow directly from the definition of W
3 The ffi-Function
In order to avoid explicitly deriving the EDF schedule in the presence of faults, we define a function,
ffi, which loosely corresponds to the "extra" work induced by a certain fault pattern, F .
Intuitively, is the amount of unfinished "extra" work that has been induced by the
fault pattern F at time t. In other words, it is the work needed above and beyond what is required
in the fault-free schedule for T . The idle time in the fault-free EDF schedule is used to do this
extra work.
The ffi -function will play an important role in the process of checking if each task meets its
deadline in EDF F (T ). Following is a method for computing ffi directly from the fault-free EDF
schedule of T and the fault pattern F .
(2)
In order to show that the above form for ffi(T ; t; F) is equivalent to W F
consider the four different cases above.
case 1: At no task can end, and thus t 0 6= e j for any j. From the definitions of W and W F ,
this implies that W (T ;
case 2: When implies that W (T which by Property
3 implies that also W F
case 3: When EDF (T ; states that W (T ; states that
j. In this case, ffi (T ; t;
case 4: When t 6= e i and EDF implies that W (T
which by Property 3 implies that also W F Hence, the -
operations in the
definitions of W and W F reduce to the usual subtraction, and it is straightforward to show
that
For illustration, Figure 1 shows an example of a task set and the corresponding values of the
function for a specific F . In this example, we consider the case in which only - 1 and - 3 may be
subject to a fault. Note that the value of ffi decreases when EDF (T ) is idle and increases at the
end of each task that is indicated as faulty in F .
R C D V223000
Fault-free
EDF Schedule

Figure

1: Task Set, EDF schedule and ffi values for f
As we have mentioned above, the ffi function is an abstraction that represents the extra work to
be performed for recovery. This extra work reduces to zero when all ready tasks complete execution
and recovery, as demonstrated by the following theorem.
Theorem in both EDF (T ) and EDF F (T ), any
task with R i - t finishes at or before time t.
Proof:
If Equation (2), this decrease in the value of the
ffi-function is only possible if EDF (T ; ", which from Property 1 leads to W (T ;
Equation (1) gives W F and the proof follows from Properties 1 and 2 ffl
4 Feasibility Test for a Task Set Under a Specific Fault Pattern
Given a task set, T , and a fault pattern, F , we now present a method for checking whether the
lowest priority task, denoted by - ' 2 T , completes by its deadline in EDF F (T ).
Theorem Given a task set, T , and a fault pattern, F , the lowest priority task, - ' , in T
completes by D ' in EDF F (T ), if and only if
Proof: To prove the if part, assume that t 0 is the smallest value such that e ' - t 0 - D ' and
are identical
from which implies that - ' completes by e ' - D ' in both schedules. If, however,
be the latest time before t 0 such that ffi(T ; - t; F) ? 0.
Note that -
is the first value after e ' at which
the definition of - t). Hence, by Theorem 1, all tasks that are ready before - t finish execution by - t
in both EDF (T ) and EDF F (T ). Moreover, ffi(T ; t; which means that
thus EDF (T ) is identical to EDF F (T ) in that period. But - ' completes
in EDF (T ) at e ' , which means that it also completes at e ' in EDF F (T ).
We prove the only if part by contradiction: assume that
finishes in EDF F (T ) at - t for some e ' - t - D ' . The fact that the lowest priority task, - ' ,
executes between time -
means that no other task is available for execution at - t \Gamma 1, and
thus 1. Given the assumption that implies that
which by Property 1 implies that EDF leads to
which is a contradiction ffl
The next corollaries provide conditions for the feasibility of EDF F (T ) for the entire task set,
T .
Corollary 1: A necessary and sufficient condition for the feasibility of EDF F (T ) for a given T
and a given F can be obtained by applying Theorem 2 to the n task sets T j ,
contains the j highest priority tasks in T .
Proof: The proof is by induction. The base case is trivial, when since there is only a single
task. For the induction step, assume that EDF F (T j ) is feasible and consider T
where - ' has a lower priority than any task in T j . In EDF F (T j+1 ), all tasks in T j will finish at
exactly the same time as in EDF F (T j ), since - ' has the lowest priority. Hence, the necessary and
sufficient condition for the feasibility of EDF F (T j+1 ) is equivalent to the necessary and sufficient
condition for the completion of - ' by D ' ffl
Corollary 2: A sufficient (but not necessary) condition for the feasibility of EDF F (T ) for a given
T and a given F is
Proof: Note that the proof of the only if part in Theorem 2 relies on the property that - ' is the
lowest priority task, which, in EDF, means the task with the latest deadline. The if part of the
theorem, however, is true even if - ' is not the lowest priority task. Hence, any - i 2 T , completes
by D i in EDF F (T ), if which proves the corollary ffl
Figure

2: The fault-tolerant schedule for the task set in Figure 1
We clarify the conditions of the above corollaries by examples. First, we show that the condition
given in Corollary 2 is not necessary for the feasibility of EDF F (T ). That is, we show that, for
any given - i , it is not necessary that in order for - i to finish
by D i in EDF F (T ). This can be seen from the example task set and fault pattern shown in Figure
1. The value of ffi(T ; t; F) is not zero between e 7.
Yet, as shown in Figure 2, - 1 and - 2 will finish by their deadlines in EDF F (T ). In other words, the
condition that stated in Theorem 2, is necessary and sufficient
for the feasibility of only the lowest priority task in EDF F (T ) (task - 4 in the above example).
Next, we show that, as stated in Corollary 1, we have to repeatedly apply Theorem 2 to all
task sets T j , to obtain a sufficient condition for the feasibility of the entire task set.
In other words, it is not sufficient to apply Theorem 2 only to T . This can be demonstrated by
modifying the example of Figure 1 such that D 7. Clearly, this change in D 3 may still result in
the same EDF schedule for T and thus will not change the calculation of Although the
application of Theorem 2 guarantees that - 4 will finish by its deadline in EDF F (T ), the recovery
of - 3 will not finish by D as seen in Figure 2.
Assume, without loss of generality, that the tasks in a given task set, T , are numbered such that
to be the extra work that still needs to be done
due to a fault pattern F , at time Noting that ffi (T ; t; F) increases only at
Equation (2) can be rewritten using the slack() function defined in Section 2 as follows:
where
The application of Theorem 2 for a given T and F requires the simulation of EDF (T ) and
the computation of e i , as well as slack(e The values of ffi i computed from
Equations (3) and (4) can then be used to check the condition of the theorem. Each step in the
above procedure takes O(n) time, except for the simulation of the EDF schedule. Such simulation
may be efficiently performed by using a heap which keeps the tasks sorted by deadlines. Each task
is inserted into the heap when it is ready and removed from the heap when it completes execution.
Since each insertion into and deletion from the heap takes O(logn) time, the total simulation of
EDF takes O(nlogn) time. Thus, the time complexity of the entire procedure is O(nlogn).
Hence, given a task set, T , and a specific fault pattern, F , a sufficient and necessary condition
for the feasibility of EDF F (T ) can be computed using Corollary 1 in O(n 2 logn) time steps. This
is less efficient than simulating EDF F (T ) directly, which can be done in O(nlogn) steps. However,
as will be described in the next section, simulating EDF (T ) only is extremely advantageous when
we consider arbitrary fault patterns rather than a specific fault pattern.
5 Feasibility Test for a Task Set Under Any Fault Pattern
We now turn our attention to determining the feasibility of a given task set for any fault pattern
with k or less faults. We use F w to denote a fault pattern with exactly w faults. That is,
We also define the function ffi w which represents the maximum extra work at time t induced
by exactly w faults that occurred at or before time t. In other words, it is the extra work induced
by the worst-case fault pattern of w faults:
Note that, although the use of F w in the above definition does not specify that all w faults will
occur at or before time t, the value of reach its maximum when all possible w faults
occur by time t.
Theorem 3 : For a given task set, T , a given number of faults w, and any fault pattern, F w , the
lowest priority task, - ' , in T completes by D ' in EDF F w
t, e ' - t - D ' .
Proof: This theorem is an extension of Theorem 2 and can be proved in a similar manner ffl
In order to compute ffi w efficiently, we define the values
and use them to compute
which is directly derived from Equation (3).
The value of each ffi w
defined as the maximum extra work at induced by any fault
pattern with w faults. This maximum value can be obtained by considering the worst scenario in
each of the following two cases:
ffl all w faults have already occurred in - . Hence, the maximum extra work at e i is
the maximum extra work at e i\Gamma1 decremented by the slack available between e i\Gamma1 and e i .
have already occurred in - additional fault occurs in - i . In this
case, the maximum extra work at e i is increased by V i , the recovery time of - i .
Hence, noting that e and the function slack() are derived from EDF (T ) and do not
depend on any particular fault pattern, the values of ffi w
can be computed for
using the following recursive formula:
\Gammaslack(e
The computations in Equation (6) can be graphically represented using a graph, G, with n
columns and k rows, where each row corresponds to a particular number of faults, w, and each
column corresponds to a particular e i (see Figure 3b). The node corresponding to row w and
column e i will be denoted by N w
. A vertical edge between N w
and N w+1
represents the execution
of one recovery block of task - i , and thus is labeled by V i . A horizontal edge between N w
and N w
means that no faults occur in task - i , and thus is labeled by -
\Gammaslack(e to indicate that the
extra work that remained at e i\Gamma1 is decremented by the slack available between e i\Gamma1 and e i . Then,
each path starting at N 0
1 in G represents a particular fault pattern (see Figure 4). The value of ffi w
corresponding to the worst case pattern of w faults at is computed from Equation 6, which
corresponds to a dynamic programming algorithm to compute the longest path from N 0
1 to N w
R
e
(a) The task set
d
slack
(b) the fault free schedule and the computation of00 04
d

Figure

3: The calculation of
4.3
e
e
d
d
d00

Figure

4: Two fault patterns for the task set of Figure 3 and the corresponding paths in G.

Figure

3 depicts an example of the computation of ffi w
i for a specific task set and 2.
The value of ffi w
i is written inside node N w
. We can see that, for this example,
from Equation (5), which satisfies the condition of Theorem 3, and thus, the lowest
priority task, - 3 , will finish before D in the presence of up to any two faults.
Similar to Corollary 1 discussed in the last section, a necessary and sufficient condition for the
feasibility of EDF F (T ) requires the repeated application of Theorem 3.
Corollary 3: A necessary and sufficient condition for the feasibility of EDF F (T ) for a given T
R C D V1 122 6 29 1
e 14e e 3(b) the fault free schedule and the computation of d
(a) The task set
d 120+2

Figure

5: An example with three tasks.
and any fault pattern F with k or less faults can be obtained by applying Theorem 3 to the n task
sets contains the j highest priority tasks in T .

Figure

5 shows the computation of ffi for an example with three tasks. Note that although the
application of Theorem 3 to this example shows that the lowest priority task, - 3 will finish by its
deadline in the presence of any two faults, the set of three tasks is not feasible in the presence of
two faults in - 1 since in this case, either - 1 or - 2 will miss the deadline. This is detected when
Theorem 3 is applied to the task set T g.
To summarize, given a task set and the maximum number of faults, k, the
following algorithm can be used to optimally check if EDF F (T ) is feasible for any fault pattern of
at most k faults.
Algorithm "Exact"
is the highest priority task in T /* the one with earliest deadline */,
is the lowest priority task (the only task) in T 1 */
ffl For do
1. Simulate EDF (T j ) and compute e well as slack(),
2. Renumber the tasks in T j such that e 1 - e j ,
3. Compute
Equation (6),
4. Let e this is just for computational convenience */
5. If ffi w
6. If (j = n) then EDF F (T ) is feasible ; EXIT.
7. Let - ' be the highest priority task in
8.
note that - ' is the lowest priority task in T j+1 */
Hence, in order to determine if the lowest priority task in a task set can finish by its deadline
in the presence of at most k faults, steps 1-5 (which apply Theorem
steps to both generate EDF (T j ) and apply Equation (6). In order to determine the feasibility of
repeat the for loop n times for
Note, however, that with some care, EDF (T j+1 ) can be derived from EDF (T j ) in at most O(n)
steps, thus resulting in a total of O(n 2 for the feasibility test. Compared with the O(n k+1 logn)
complexity required to simulate EDF under the possible O(n k ) fault patterns, our algorithm has a
smaller time complexity, even for
As indicated in Corollary 2, a sufficient but not necessary feasibility test may be obtained by
computing ffi from a simulation of EDF (T ), and then making sure that, for each task - i , ffi is equal
to zero between e i and D i . This can be completed in O(nlog(n)+nk) time as shown in the following
algorithm.
Algorithm "Sufficient"
1. Simulate EDF (T ) and compute e as well as slack(),
2. Renumber the tasks in T j such that e 1 - e n ,
3. Compute
Equation (6),
4. Let e this is just for computational convenience */
5. For do
d
d
tee
d 200 0021
(a) The task set (b) the computation of d

Figure

An example in which f - can tolerate any two faults
The example shown in Figure 6 shows that a task - i ,
even if the value of ffi computed from the simulation of EDF (T ) does not equal zero between e i and
. In this example,
Yet, it is easy to see that
the shown EDF schedule can tolerate any two faults (two faults in - 1 , two faults in - 2 or one fault
in each of - 1 and - 2 ). To intuitively explain this result, we note that, although
2 represents the
maximum recovery work that needs to be done at no information is kept about the priority
at which this recovery work will execute in EDF F (T ). Specifically, in the given example, some of
the work in ffi 2
will execute in EDF F (T ) at the priority of - 1 , which is lower than the priority of
Thus, it is not necessary that
to finish before its deadline. This, in
general, may happen only because it is possible for a lower priority task to finish before a higher
priority task. That is, if for some i and j, e
Finally, we note that, from the observation given in the last paragraph, algorithm "Sufficient"
will provide a sufficient and necessary feasibility test in the special case where tasks complete
execution in EDF (T ) in the order of their priorities (deadlines). That is, if computed
from EDF (T ) satisfy e i - e i+1 and D i - D i+1 . In this case, the recovery work in any ffi w
would
have to execute in EDF F (T ) at a priority higher than or equal to that of - i , and thus it is necessary
for this work to be completed by D i if - i is to complete by its deadline.
6 Related Work
Earlier work dealing with tolerance to transient faults for aperiodic tasks was carried out from the
perspective of a single fault in the system [LC88, KS86]. More recently, the fault models were
enhanced to encompass a single fault occurring every interval of time, for both uniprocessors and
multiprocessor systems [BJPG89, GMM94, GMM97]. Further, tolerance to transient faults for
periodic tasks has also been addressed for uniprocessors [RT93, RTS94, OS94, PM98, GMM98] and
multiprocessor systems [BMR99, OS95, LMM98].
In [KS86], processor failures are handled by maintaining contingency or backup schedules. These
schedules are used in the event of a processor failure. To generate the backup schedule, it is assumed
that an optimal schedule exists and the schedule is enhanced with the addition of "ghost" tasks,
which function primarily as standby tasks. Since not all schedules will permit such additions, the
scheme is optimistic. More details can be found in [KS97].
Duplication of resources have been used for fault-tolerance in real-time systems [OS92]. How-
ever, the algorithm presented is restricted to the case where all tasks have the same period. More-
over, adding duplication for error recovery doubles the amount of resources necessary for scheduling.
In [BJPG89], a best effort approach to provide fault tolerance has been discussed in hard real-time
distributed systems. A primary/backup scheme is used in which both the primary and the
backup start execution simultaneously and if a fault affects the primary, the results of the backup
are used. The scheme also tries to balance the workload on each processor.
More recently, work has been done on the problem of dynamic dispatching algorithms of frame-based
computations with dynamic priorities, when one considers a single fault. In [LLMM99], it
was shown that simply generating n EDF schedules, one for each possible task failure, is sufficient
to determine if a task set can be scheduled with their deadlines. Also, the work in [Kop97] describes
the approach taken by the Mars system in frame-based fault tolerance. Mars was a pioneer system
in the timeline dispatching of tasks through the development of time-triggered protocols. It takes
into account the scheduling overhead, as well as the need for explicit fault tolerance in embedded
real-time systems. However, MARS requires special hardware to perform fault-tolerance related
tasks such as voting and, thus, it cannot be used in a broad range of real-time systems.
7 Conclusion
We have addressed the problem of guaranteeing the timely recovery from multiple faults for aperiodic
tasks. In our work, we assumed earliest-deadline-first scheduling for aperiodic preemptive
tasks, and we developed a necessary and sufficient feasibility-test for fault-tolerant admission con-
trol. Our test uses a dynamic programming technique to explore all possible fault patterns in the
system, but has a complexity of O(n 2 \Delta k), where n is the number of tasks to be scheduled and k is
the maximum number of faults to be tolerated.
EDF is an optimal scheduling policy for any task set T in the sense that, if any task misses its
deadline in EDF (T ), there is no schedule for T in which no deadlines are missed. EDF is also an
optimal fault-tolerant scheduling policy. Specifically, EDF F (T ) for a fault pattern F is equivalent
to EDF (T 0 ) where T 0 is obtained from T by replacing the computation time, C i , of each task - i in
Hence, the work presented in this paper answers the following question optimally:
Given a task set, T , is there a feasible schedule for T that will allow for the timely
recovery from any combination of k faults?

Acknowledgments

The authors would like to thank Sanjoy Baruah for proposing the problem of tolerating k faults
in EDF schedules and for valuable discussions and feedback during the course of this work. The
authors would also like to acknowledge the support of DARPA through contract DABT63-96-C-
0044 to the University of Pittsburgh.



--R

Workload Redistribution for Fault Tolerance in a Hard Real-Time Distributed Computing System

Layered control of a Binocular Camera Head.
Single Event Upset Rates in Space.
Derivation and Caliberation of a Transient Error Reliability Model.

Implementation and Analysis of a Fault-Tolerant Scheduling Algorithm


A Program Structure for Error Detection and Recovery.
A Measurement-Based Model for Workload Dependence of CPU Errors
Measurement and Modeling of Computer Reliability as Affected by System Activity.

On Scheduling Tasks with a Quick Recovery from Failure.

A Fault-tolerant Scheduling Problem
Architectural Principles for Safety-Critical Real-Time Applications
Global Fault Tolerant Real-Time Scheduling on Multiprocessors
An Efficient RMS Admission Control and its Application To Multiprocessor Scheduling.
An Imprecise Real-Time Image Magnification Algorithm
An Algorithm for Real-Time Fault-Tolerant Scheduling in a Multiprocessor System
Enhancing Fault-Tolerance in Rate-Monotonic Scheduling
Allocating Fixed-Priority Periodic Tasks on Multiprocessor Sys- tems
Minimum Achievable Utilization for Fault-tolerant Processing of Periodic Tasks
Fault Tolerant Computing: Theory and Techniques.
Enhancing Fault Tolerance of Real-Time Systems through Time Redundancy
Scheduling Fault Recovery Operations for Time-Critical Applications
Algorithm Based Fault Tolerance for Matrix Inversion With Maximum Pivoting.
--TR

--CTR
Alireza Ejlali , Marcus T. Schmitz , Bashir M. Al-Hashimi , Seyed Ghassem Miremadi , Paul Rosinger, Energy efficient SEU-tolerance in DVS-enabled real-time systems through information redundancy, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
Alireza Ejlali , Bashir M. Al-Hashimi , Marcus T. Schmitz , Paul Rosinger , Seyed Ghassem Miremadi, Combined time and information redundancy for SEU-tolerance in energy-efficient real-time systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.4, p.323-335, April 2006
Xiao Qin , Hong Jiang, A novel fault-tolerant scheduling algorithm for precedence constrained tasks in real-time heterogeneous systems, Parallel Computing, v.32 n.5, p.331-356, June 2006
real-time scheduling;fault-tolerant schedules;fault recovery;earliest-deadline first