@MASTERSTHESIS\{IMM2007-05442,
    author       = "J. P. Kany and S. H. Madsen",
    title        = "Design Optimisation of Fault-Tolerant Event-Triggered Embedded Systems",
    year         = "2007",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Prof. Paul Pop, {IMM,} {DTU}.",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/5442-full.html",
    abstract     = "Computers today are getting smaller and cheaper and are almost everywhere in our daily lives: at our homes, in the cars, airplanes and industry – almost all devices we use contains one or more embedded computers. With growing usage of embedded devices the requirements are getting tighter. In this thesis we address safety-critical embedded systems, where not only the correct result, but also satisfying timing requirements of the system is vital even in the presence of faults.

The increase in computational speed and circuit density has raised the probability of having transient faults. Embedded systems that are used in safety-critical applications must be able to tolerate the increasing number of transient faults. If not, they might lead to failures that would have disastrous consequences and potentially endanger human lives and the environment.

This thesis addresses design optimisation for fault-tolerant event-triggered embedded systems. The hardware of these systems consists of distributed processing elements connected with communication busses. The applications to be run on the hardware are represented by directed acyclic graphs. Processes are scheduled using a fixed-priority preemptive scheduling policy, while messages are transmitted using the Controller Area Network bus protocol. Faults are tolerated for each process through either reexecution or active replication.

In this thesis we describe a model for representing fault-tolerant applications, called fault-tolerant process graphs (FTPG). We first propose schedulability analysis techniques which can determine whether a fault-tolerant application represented using an {FTPG} is schedulable. Three different approaches to the schedulability analysis have been proposed: ignoring conditions (IC), condition separation (CS) and brute force analysis (BF). They differ in the quality of the results and their runtime. Considering the response-time analysis, we also present an optimisation heuristic that decides for each process which faulttolerance policy to use, and on which processing element to execute it, such that the application is schedulable.

We have evaluated the proposed schedulability analysis and optimisation methods using randomly-generated synthetic applications and a cruise controller application from the automotive industry."
}