Off-line Real-Time Fault-Tolerant Scheduling (joint work with A. Girault, C. Lavarenne & Y. Sorel)

We address the problem of off-line fault tolerant scheduling of an algorithm onto a multiprocessor architecture with distributed memory and provide a generic algorithm which solves this problem. We take into account two kinds of failures: fail-silent and omission. The basic technique we use is the replication of operations and data communications. We then discuss the principles which govern the execution of schedulings with replication under the state-machine and the primary/backup arbitrations between replicas. We also show how to compute the execution date for each operation and the timeouts which are used for detecting failures. We end with a heuristic which, using this calculus, computes a possibly non optimal scheduling by finding plain schedulings for each failure pattern and then combining them into a scheduling with replication.

"Proceedings of 9th Euromicro Workshop on Parallel and Distributed Processing", Mantova, Italy, February 2001, IEEE Computer Society Press, pages 410-417, 2001.

 gzipped postscript file.