Fault‐Tolerant Real‐Time Scheduling

We use competitive analysis to study how best to use redundancy to achieve fault‐tolerance in online real‐time scheduling. We show that the optimal way to use spatial redundancy depends on a complex interaction of the benefits, execution times, release times, and latest start times of the jobs. We give a randomized online algorithm whose competitive ratio is O( logΦ log Delta ( log ² n log m/ log log m)) for transient faults. Here n is the number of jobs, m is the number of processors, Φ is the ratio of the maximum value density of a job to the minimum value density of a job, and Δ is the ratio of the longest possible execution time to the shortest possible execution time. We show that this bound is close to optimal by giving an Ω(( log ΔΦ/ log log m) ( log m log log m) ² ) lower bound on the competitive ratio of any randomized algorithm. In the case of permanent faults, there is a randomized online algorithm that has a competitive ratio of O( log Phi log Δ (log m/log log m)). We also show a lower bound of Ω((log ΔΦ/ log log m) ( log m/log log m)) on the competitive ratio for interval scheduling with permanent faults.