loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2003 International Conference on Dependable Systems and Networks (DSN'03)
An Algorithm for Automatically Obtaining Distributed and Fault-Tolerant Static Schedules
San Francisco, California
June 22-June 25
ISBN: 0-7695-1952-0
Our goal is to automatically obtain a distributed and fault-tolerant embedded system: distributed because the system must run on a distributed architecture; fault-tolerant because the system is critical. Our starting point is a source algorithm, a target distributed architecture, some distribution constraints, some indications on the execution times of the algorithm operations on the processors of the target architecture, some indications on the communication times of the data-dependencies on the communication links of the target architecture, a number Npf of fail-silent processor failures that the obtained system must tolerate, and finally some real-time constraints that the obtained system must satisfy. In this article, we present a scheduling heuristic which, given all these inputs, produces a fault-tolerant, distributed, and static scheduling of the algorithm on the architecture, with an indication whether or not the real-time constraints are satisfied. The algorithm we propose consist of a list scheduling heuristic based active replication strategy, that allows at least Npf +1 replicas of an operation to be scheduled on different processors, which are run in parallel to tolerate at most Npf failures. Due to the strategy used to schedule operations, simulation results show that the proposed heuristic improve the performance of our method, both in the absence and in the presence of failures.
Index Terms:
Fault Tolerance in Distributed and Real-Time Systems, Safety-Critical Systems, software implemented fault-tolerance, multi-component architectures, distribution heuristics
Citation:
Alain Girault, Hamoudi Kalla, Mihaela Sighireanu, Yves Sorel, "An Algorithm for Automatically Obtaining Distributed and Fault-Tolerant Static Schedules," dsn, pp.159, 2003 International Conference on Dependable Systems and Networks (DSN'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.