Fault-tolerant scheduling
Bala Kalyanasundaram, Kirk R. Pruhs · 1994
We study fault-tolerant multiprocessor nonpreemptive scheduling under the realistic assumption that the occurrence of faults can not be predicted.The goal in these problems is to minimize the delay incurred by the jobs.Since this is an on-line problem we use competitive analysis to evaluate possible algorithms.For the problems of minimizing the make-span, and minimizing the average response time (for static release times), we give nonclairvoyant algorithms (both deterministic and randomized) that have provably asymptotically optimal competitive ratios.The main tool used by these algorithms to combat faults is redundancy.We show that randomization has the same effect as redundancy.work on scheduling either assumes that there are