On scheduling Tasks with a Quick Recovery from failure

Abstract- Multiprocessors used in life-critical real-time sys-tems must recover quickly from failure. Part of this recovery consists of switching to a new task schedule that ensures that hard deadlines for critical tasks continue to be met. We present a dynamic programming algorithm that ensures that backup, or contingency, schedules can be efficiently embedded within the original, "primary " schedule to ensure that hard deadlines con-tinue to be met in the face of up to a given maximum number of processor failures. Several illustrative examples are included. Index Terms-Fault-tolerant and real-time multiprocessors, hard deadlines, primary and contingency schedules, primary and ghost clones, notification times. I