Fault-Tolerant Real-Time Scheduling |
| |
Authors: | B Kalyanasundaram K Pruhs |
| |
Affiliation: | (1) Department of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260, USA. kalyan@cs.pitt.edu, kirk@cs.pitt.edu., US |
| |
Abstract: | 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
2
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)
2
) 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.
Received October 1997; revised January 1999. |
| |
Keywords: | , Fault-tolerant scheduling, Real-time scheduling, Competitive analysis, |
本文献已被 SpringerLink 等数据库收录! |
|