Fault-tolerance is the ability of a system to maintain its functionality, even in the presence of faults. It has been extensively studied in the literature: [ALRL04] and [Lap04] gives an exhaustive list of the basic concepts and terminology on fault-tolerance, [Pow92] introduces two fundamental notions for fault-tolerance, namely failure mode assumption and assumption coverage, and [Gär99] formalizes the important underlying notions of fault-tolerance. Concerning more specifically real-time systems, [Rus94] gives a short survey and taxonomy for fault-tolerance and real-time systems, and [Cri93,Jal94] treat in details the special case of fault-tolerance in distributed systems.

If you want to be convinced of the impact of faults and failures, you can browse the following pages:

• Collection of Software Bugs
• Computer horror stories

The three basic notions are fault, failure, and error: a fault is a defect or flaw that occurs in some hardware or software component; an error is a manifestation of a fault; a failure is a departure of a system from the service required. A failure in a sub-system may be seen as a fault in the global system. Hence the following causal relationship:

Consider for instance a system running on a multi-processor architecture: a fault in one processor might cause it to crash (i.e., a failure), which will be seen as a fault of the system. Therefore, the ability of the system to function even in the presence of the failure of one processor will be regarded as fault-tolerance instead of failure-tolerance.

Not all faults cause immediate failure: faults may be latent (activated but not apparent at the service level), and later become effective. Fault-tolerant systems attempt to detect and correct latent errors before they become effective. Faults are classified according to the following criteria:

• by their nature: accidental or intentional;
• by their origin: physical, human, internal, external, conception, operational;
• by their persistence: transient or permanent.

Failures are classified according to the following criteria:

• by their domain: failures on values and/or timing failures;
• by their perception by the user;
• by their consequences on the environment.

The means for fault-tolerance are either:

• error processing (to remove errors from the system's state), which can be carried out either with recovery (rolling back to a previous correct state) or with compensation (masking errors using the internal redundancy of the system);

• fault treatment (to prevent faults from being activated again), which is carried out in two steps: diagnostic (determining the cause, location, and nature of the error) and then passivation (preventing the fault from being activated again).

Theses means use redundancy in order to treat errors, of which three forms exist: hardware redundancy (e.g., using a spare processor), software redundancy (e.g., using two implementations of the same module), and time redundancy (e.g., re-executing a module later).

Finally, two things are important when designing fault-tolerant systems: the fault hypothesis (what type of fault do we want the system to tolerate) and the fault coverage (the probability that the fault hypothesis be respected when a fault actually occurs in the system).

    La Bique allant remplir sa traînante mamelle
    Et paître l'herbe nouvelle,
    Ferma sa porte au loquet,
    Non sans dire à son Biquet :
    Gardez-vous sur votre vie
    D'ouvrir que l'on ne vous die,
    Pour enseigne et mot du guet :
    Foin du Loup et de sa race !
    Comme elle disait ces mots,
    Le Loup de fortune passe ;
    Il les recueille à propos,
    Et les garde en sa mémoire.
    La Bique, comme on peut croire,
    N'avait pas vu le glouton.
    Dès qu'il la voit partie, il contrefait son ton,
    Et d'une voix papelarde
    Il demande qu'on ouvre, en disant Foin du Loup,
    Et croyant entrer tout d'un coup.
    Le Biquet soupçonneux par la fente regarde.
    Montrez-moi patte blanche, ou je n'ouvrirai point,
    S'écria-t-il d'abord. (Patte blanche est un point
    Chez les Loups, comme on sait, rarement en usage.)
    Celui-ci, fort surpris d'entendre ce langage,
    Comme il était venu s'en retourna chez soi.
    Où serait le Biquet s'il eût ajouté foi
    Au mot du guet, que de fortune
    Notre Loup avait entendu ?
    Deux sûretés valent mieux qu'une,
    Et le trop en cela ne fut jamais perdu. 

    Deux sûretés valent mieux qu'une,
    Et le trop en cela ne fut jamais perdu. 

    Two safeties are better than one,
    And too much in this respect was never a loss.

In the past, we have been involved in a French "Action de Recherche Coordonnée" funded by Inria, named Tolère, and a European Research Project dealing with embedded electronics for automotive, named EAST-EEA, and involving various automotive industries and research labs.

3.1. New scheduling/distribution heuristics

Researchers involved: Girault, Sorel, Lavarenne, Sighireanu, Dima, Pinello, Kalla, Assayad, Leignel, Yu, and Leveque.

Our personal contribution to research in the fault-tolerant embedded systems consists of several scheduling/distribution heuristics. Their common feature is to take as an input two graphs: a data-flow graph ALG describing the algorithm of the application, and a graph ARC describing the target distributed architecture. Below to the left is an example of an algorithm graph: it has nine operations (represented by circles) and eleven data-dependences (represented by green arrows). Among the operations, one is a sensor operation (I), one is an actuator operation (O), while the seven others are computations (A to G). Below to the right is an example of an architecture graph: it has three processors (P1, P2, and P3) and three point-to-point communication links (L1.2, L1.3, and L2.3).

Also given is a table giving the Worst-Case Execution Time (WCET) of each operation onto each processor, and the worst-case transmission time of each data-dependence onto each communication link. The architecture being a priori heterogeneous, these need not be identical. Below is an example of such a table for the operations of ALG. The infinity sign expresses the fact that the operation I cannot be executed by the processor P3, for instance to account for the requirement of certain dedicated hardware.

Form these three inputs, the heuristic distributes the operations of ALG onto the processors of ARC and schedules them statically, as well as the communications induced by these scheduling decisions. The output of the heuristic is therefore a static schedule, from which embeddable code can be generated.

For the embeddable code generation, we use SynDEx, a system level CAD software based on the "Algorithm-Architecture Adequation" (AAA) methodology, for rapid prototyping and optimizing the implementation of distributed real-time embedded applications onto "multicomponent" architectures. It has been designed and developed at INRIA by the AOSTE team. Also, our heuristics are implemented inside SynDEx, as an alternative to its own default heuristics (called DSH: Distribution Scheduling Heuristic [GLS99]).

Our fault hypothesis is that the hardware components are fail silent, meaning that a component is either healthy and works fine, or is faulty and produces no output at all. Recent studies on modern hardware architectures have shown that a fail-silent behavior can be achieved at a reasonable cost [BFM+03], so our fault hypothesis is reasonable.

Our contribution consists of the definition of several new scheduling/distribution heuristics in order to generate static schedules that are in addition tolerant to a fixed number of hardware components (processors and/or communication links) faults. These new heuristics include:

• FTBAR (Fault-Tolerant Based Active Replication) generates a static schedule that tolerates Npf processor faults, by replicating actively all the operations of the algorithm graph ALG exactly Npf+1 times. It works with target architectures having either point-to-point communication links or buses, but assumes that all the communication links are reliable. FTBAR tries to minimize the critical path of the obtained schedule w.r.t. the know WCETs of the operations onto the various processors of the architecture [GKS06] [Kal04] [GKS04b] [GKS03] [GKSS03] [GLSS01a] [GLSS01b] [GLSS00].

• RBSA (Reliable Bicriteria Scheduling Algorithm) generates a reliable and static schedule, also by replicating actively the operations of the algorithm graph. The difference with FTBAR is that the number of times an operation is replicated depends on the individual reliability of the processors it is scheduled on and on the overall reliability level required by the user. RBSA tries both to minimize the critical path of the obtained schedule and to maximize its reliability (these are the two criteria of this heuristic). Unlike all bicriteria (length,reliability) scheduling heuristics found in the literature, RBSA is the only one that can actually increase the reliability of the obtained system, because it is the only scheduling heuristics that actively replicates the operations and communications [AGK04].

• BSH (Bicriteria Scheduling Heuristics) solves a difficult problem inherent to all bicriteria (length,reliability) scheduling heuristics. This problem is due to the fact that the reliability criterion is intrinsically dependent on the length criterion (under the classical exponential failure model of Shatz and Wang), and incurs three major drawbacks: first, the length criterion overpowers the reliability criterion; second, it is very tricky to control precisely the replication factor of the operations onto the processors, from the beginning to the end of the schedule (in particular, it can cause a "funnel" effect); and third, the reliability is not a monotonous function of the schedule. To solve this problem, we propose a new criterion instead of the reliability, which we call the Global System Failure Rate (GSFR); the GSFR is the failure rate per time unit of the system, seen as if it was a single operation placed onto a single processor. We have conducted extensive simulations that demonstrate that our new bicreteria (length,GSFR) scheduling algorithm BSH avoids all the problems that plague the classical (length,reliability) scheduling heuristics found in the literature, which we mentioned above [GK09].

• TSH (Tricriteria Scheduling Heuristics) extends BSH with the power consumption criterion. From a given software application graph ALG and a given multiprocessor architecture ARC, produces a static multiprocessor schedule that optimizes three criteria: its length (crucial for real-time systems), its reliability (crucial for dependable systems), and its power consumption (crucial for autonomous systems). TSH uses the active replication of the operations and the data-dependencies to increase the reliability, and uses dynamic voltage scaling (DVS) to lower the power consumption. Moreover, we show that, to produce the Pareto surface of the best tradeoffs between the three criteria, it is necessary to transform two of the criteria into constraints, and then optimize the third criterion under those two constraints. This in turn requires that the constraints are invariant measures of the schedule under construction. This is because list scheduling heuristics cannot backtrack. For example, we use the power consumption and not the total energy consumed, because the energy is not an invariant measure of the schedule: indeed, if S' is a prefix schedule of S, then E(S) > E(S'). It follows that ensuring that E(S') is less than the energy constraint Eobj does not ensure that E(S) is less than Eobj. For the same reason, we use the GSFR (Global System Failure Rate --- see the previous item) rather than the reliability [AGK12a] [AGK12b] [AGK11].

• GRT + eDSH (Graph Redundancy Transformation + extended Distribution Scheduling Heuristic) generates a static schedule that tolerates Npf processor faults and Nlf communication link faults. It first transforms the algorithm graph ALG into another data-flow graph ALG* by adding redundancy into it such that the required number of hardware component faults will be tolerated. During this phase, it also generates exclusion relations between subsets of operations that must be scheduled onto distinct processors, and subsets of data dependences that must be routed through disjoint paths. Then it uses an extended version of the DSH heuristics to generate a static schedule of ALG* onto ARC, w.r.t. the exclusion relations generated during the first phase [GKS04a].

• FPMH (Fault Patterns Merging Heuristic) is an original approach to generate a static schedule of ALG onto ARC tolerant to a given list of fault patterns. A fault pattern is a subset of the architecture's component that can fail simultaneously. Our methods involves two steps. First, for each fault pattern, we generate the corresponding reduced architecture (the architecture from which the pattern's component have been removed), and we generate a static schedule of ALG onto this reduced architecture (we use the basic DSH heuristic of SYnDEx for this). From N fault patterns, we therefore obtain N basic schedules. The second step consists of the merging of these N basic schedules into one static schedule that will be, by construction, tolerant to all the specified fault patterns [DGLS01]. The merging operation raises a number of theoretical and practical problems that were hard to solve elegantly and efficiently!

3.2. Discrete controller synthesis

Researchers involved: Girault, Rutten, Abdennebi, Dumitrescu, Taha, Marchand, and Sun.

Another of our contributions (not a heuristic this time) was the usage of discrete controller synthesis theory [RW87] to generate automatically fault-tolerant software. The principle is to design a software (for instance to control some plant) by taking into account all possible behaviors, i.e., both the good ones and the bad ones (the faults). Then, we have considered that all the fault events were uncontrollable. We have added to the system an environment model that specifies what fault events can occur simultaneously. The advantage of discrete controller synthesis is that it is able to produce automatically a controller that, put in parallel with the system, controls it in such a manner that it satisfies some predefined safety requirements. In our approach, these requirements express precisely the fault tolerance. We have conducted several studies on this approach that prove its feasibility and its elegance. From the point of view of fault-tolerance, our approach is interesting in the sense that, when the controller synthesis actually succeeds in producing a controller, we obtain a system equipped with a dynamic reconfiguration mechanism to handle faults, with a static guarantee that all specified faults will be tolerated during the execution, and with a known bound on the system's reaction time (thanks to optimal controller synthesis) [DGMR10] [GR09] [DGMR07b] [DGMR07a] [DGR04] [GR04]. New developments are towards the efficient implementation of the synthesized fault-tolerant controlled systems, by using the LibDGALS library for dynamic GALS systems.

3.3. Aspect oriented programming: fault-tolerant programs and fault-tolerant circuits

Researchers involved: Fradet, Girault, Ayav, and Burlyaev.

We are investigating the use of aspect oriented programming [KLM⁺97] [BSL01] for transforming automatically a non fault-tolerant program into a fault-tolerant one. As a first step in this direction, we have proposed several automatic program transformations (i.e., no an aspect language yet) to insert automatically heartbeats and checkpoints in a real-time distributed program. We have formalized these transformations as rewriting rules in ML for a simple programming language (with assignment, if-then-else, for loops, and input/output). Our contribution is twofold. First we have formally proved that our transformations preserve the semantics of initial program and we have derived formulas to compute the WCET of the obtained program (this WCET can then be checked against the real-time constraints). Second, choosing the lengths of checkpointing and heartbeating intervals is delicate. Long intervals lead to long roll-back time, while too frequent checkpointing leads to high overheads. We have derived formulas for choosing the optimal checkpointing and hearbeating intervals. As a result, the overhead due to adding the fault-tolerance is minimized [AFG08] [AFG06].

New developments concern fault-tolerant circuits for which we want to propose automatic transformation procedures. These procedures will turn an initial non fault-tolerant circuit into a new fault-tolerant circuit (for instance by replicating portions of the circuits, by adding voters, or by adding error correction blocks). We will also seek to prove formally the correctness of there procedure, manually or with the help of a theorem prover.

3.4. Probabilistic contracts for reliable components

Researchers involved: Xu, Goessler, and Girault.

We are working on a probabilistic contract framework for describing and analysing component-based embedded systems, based on the theory of Interactive Markov Chains (IMC). A contract specifies the assumptions a component makes on its context and the guarantees it provides. Probabilistic transitions allow for uncertainty in the component behavior, e.g. to model observed black-box behavior (internal choice) or reliability. An interaction model specifies how components interact. We provide the ingredients for a component-based design flow, including (1) contract satisfaction and refinement, (2) parallel composition of contracts over disjoint, interacting components, and (3) conjunction of contracts describing different requirements over the same component. By using parametric probabilities in the contracts, we are able to answer questions such as "what is the most permissive component which satisfies a given contract?" [GXG12] [XGG10].