Generation of fault-tolerant static scheduling for real-time distributed embedded systems with multi-point links

Abstract

We describe a solution to automatically produce distributed and fault-tolerant code for real-time distributed embedded systems. The failures supported are processor failures, with fail-stop behavior. Our solution is grafted on the "Algorithm Architecture Adequation" method (AAA), used to obtain automatically distributed code. The heart of AAA is a scheduling heuristic that produces automatically a static distributed schedule of a given algorithm onto a given distributed architecture. We design a new heuristic in order to obtain a static, distributed and fault-tolerant schedule. The new heuristic schedules supplementary replicas for each computation operation of the algorithm to be distributed and the corresponding communications, where is the number of processor failures intended to be supported. In the same time, the heuristic statically computes the main replica after each failure, such that the execution time is minimized. The analysis of this heuristic shows that it gives better results for distributed architectures using multi-point, reliable links. This solution corresponds to a software implemented fault-tolerance, by mean of software redundancy of algorithm's operations and timing redundancy of communications.