A Fault-Tolerant Scheduling Algorithm Based on Checkpointing and Redundancy for Distributed Real-Time Systems

Literature Review

Extensive research has been presented to investigate the software-based fault tolerance techniques against transient faults. In the software replication technique (Girault et al., 2004; Assayad et al., 2012; Samal et al., 2013; Meroufel & Belalem, 2014) multiple replicas (active or passive) of each task are executed on different processors.

Assayad et al. (2012) proposed a new tri-criteria scheduling heuristic to minimize the schedule length, the global system failure rate and the power consumption of the generated schedule. Active replication of tasks and data dependencies is used to increase the system reliability. The primary-backup approach (passive replication) is used as a fault-tolerant scheduling technique in (Samal et al., 2013) to guarantee real time tasks constraints in the presence of permanent or transient faults. The authors proposed fault-tolerant scheduling for independent tasks using a hybrid genetic algorithm.

The replication technique is effective to tolerate spatial multiple faults (permanent or transient) and it is more preferable for safety-critical systems (Ejlali et al., 2012). However, scheduling multiple replicas of each task on different processors may not be affordable due to cost constraints (Ropars et al., 2015).

Checkpointing with rollback recovery (Han et al., 2015; Izosimov et al., 2012; Wei et al., 2012; Zhang & Chakrabarty, 2006; Kumar et al. 2015) and re-execution (Izosimov et al., 2008; Gui & Luo, 2013) are classified by Motaghi and Zarandi (2014) as time-based redundancy methods. These methods try to deal with transient faults by serial executions in the same processor of faulty task. Izosimov et al. (2008) proposed a quasi-static scheduling of fault tolerant embedded systems composed of hard and soft processes. In which re-execution is employed to recover from multiple faults. Han et al. (2015) presented a task allocation scheme for minimizing energy consumption while ensuring the fault tolerance requirement of the system. They develop an efficient method to determine the checkpointing scheme to tolerate k transient faults on a single processor. These methods do not impose any hardware cost overhead and are not effective to tolerate transient faults whose durations are very long. Moreover, serial execution may cause the non-respect of time constraints.