Design optimization of time- and cost-constrained fault-tolerant embedded systems with checkpointing and replication

Abstract—We present an approach to the synthesis of fault-tol-erant hard real-time systems for safety-critical applications. We use checkpointing with rollback recovery and active replication for tolerating transient faults. Processes and communications are statically scheduled. Our synthesis approach decides the assign-ment of fault-tolerance policies to processes, the optimal place-ment of checkpoints and the mapping of processes to processors such that multiple transient faults are tolerated and the timing con-straints of the application are satisfied. We present several design optimization approaches which are able to find fault-tolerant im-plementations given a limited amount of resources. The developed algorithms are evaluated using extensive experiments, including a real-life example. Index Terms—Fault tolerance, processor scheduling, real time systems, redundancy. I