FORMATS-FTRTFT 2004 START ConferenceManager    

Static fault-tolerant scheduling with ``pseudo-topological'' orderings

Catalin Dima, Alain Girault, Yves Sorel

Presented at Formal Modelling and Analysis of Timed Systems - Formal Techniques in Real-Time and Fault Tolerant System (FORMATS-FTRTFT 2004), Grenoble, France, September 22-24, 2004


We give a graph-theoretical model for off-line fault-tolerant scheduling of dataflow algorithms onto multiprocessor architectures with distributed memory. Our framework allows the modeling of both processor and channel failures of the ``fail silent'' type (either transient or permanent), and failure masking is achieved by replicating operations and data communications. We show that, in general, the graph representing a fault-tolerant scheduling may have circuits; hence, the classical computation of starting/ending times, based upon a topological ordering, is inapplicable. We then provide a notion of ``pseudo-topological ordering'' that permits the computation of the starting/ending times even in the case of cyclic graphs. We also derive algorithms for computing the timeouts that are used for failure detection.

START Conference Manager (V2.47.2)