Real-time systems are being increasingly used in several applications which
are time-critical in nature. Fault tolerance is an essential requirement o
f such systems, due to the catastrophic consequences of not tolerating faul
ts. In this paper, we study a scheme that guarantees the timely recovery fr
om multiple faults within hard real-time constraints in uniprocessor system
s. Assuming earliest-deadline-first scheduling (EDF) for aperiodic preempti
ve tasks, we develop a necessary and sufficient feasibility-check algorithm
for fault-tolerant scheduling with complexity O(n(2). k), where n is the n
umber of tasks to be scheduled and k is the maximum number of faults to be
tolerated.