Scheduling of replicated tasks to meet correctness requirements and deadlines

The authors consider a coarse-grained multiprocessing environment in which multiple task copies or unreliable versions referred to as task instances need to be scheduled to run on unreliable processors in the face of correctness and timeliness requirements that are considered met if c task instances run to correct completion before the deadline d. The authors study the interplay of correctness and timeliness requirements, providing examples of how scheduling policies that are optimal in other contexts can fail to meet correctness and timeliness needs in this environment. Optimal scheduling policies for certain special cases of the problem are presented, followed by a discussion of heuristics with reasonable performance in more general cases