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 Phi 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, Phi 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 Δ Phi/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 Δ Phi/log log m) (log m/log log m)) on the competitive ratio for interval scheduling with permanent faults.
