A new approach to fault-tolerant scheduling using task duplication in multiprocessor systems

In this paper we propose a new approach to fault-tolerant scheduling of parallel programs in multiprocessor systems. It is well known that inter-processor communication makes serious effects on the performance of parallel processing, and that task duplication is an effective technique to reduce overheads of communication. Though it was originally developed only for improving performance, we propose the use of this technique also for achieving fault-tolerance. Based on this approach, we develop a scheduling algorithm for tolerating a single processor failure. This algorithm duplicates all tasks of a program and allocates them to processors so as to eliminate communication delays as much as possible. The experimental results show that the obtained schedules can achieve fault-tolerance at the cost of small degree of time redundancy. (C) 2000 Elsevier Science Inc. All rights reserved.