Algorithms for testing fault-tolerance of sequenced jobs

作     者：Chrobak, Marek Hurand, Mathilde Sgall, Jiri 

作者机构：Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Ecole Polytech Dept Informat LIX Palaiseau France Charles Univ Prague Dept Appl Math CR-11800 Prague 1 Czech Republic 

出 版 物：《JOURNAL OF SCHEDULING》 (调度杂志)

年 卷 期：2009年第12卷第5期

页      面：501-515页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0802[工学-机械工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Scheduling Fault-tolerance Real-time systems Algorithms 

摘      要：We study the problem of testing whether a given set of sequenced jobs can tolerate transient faults. We present efficient algorithms for this problem in several fault models. A fault model describes what types of faults are allowed and specifies assumptions on their frequency. Two types of faults are considered: hidden faults, that can only be detected after a job completes, and exposed faults, that can be detected immediately. First, we give an O(n)-time fault-tolerance testing algorithm, for both exposed and hidden faults, if the number of faults does not exceed a given parameter k. Then we consider the model in which any two faults are separated in time by a gap of length at least Delta, where Delta is at least twice the maximum job length. For exposed faults, we give an O(n)-time algorithm. For hidden faults, we give an algorithm with running time O(n(2)), and we prove that if job lengths are distributed uniformly over an interval [0, p(max)], then this algorithm s expected running time is O(n). Our experimental study shows that this linear-time performance extends to other distributions. Finally, we provide evidence that improving the worst-case performance may not be possible, by proving an Omega(n(2)) lower bound, in the algebraic computation tree model, on a slight generalization of this problem.