An efficient recovery procedure for fault tolerance in distributed systems
Abstract In this article, the problem of fault tolerance in real-time distributed systems is addressed by providing an efficient algorithmic procedure for recovery in such systems. Our recovery procedure does not require the application of an intrusive checkpointing procedure, but uses contextual information exchanged between the distributed system components during normal system progress. On detection of a failure, each process, through an efficient propagation mechanism, will have locally computed a recovery point that is mutually consistent with the recovery points computed by other processes. During recovery, each process considers the contextual information recorded after its established recovery point; a minimal amount of computations are redone. Also, a minimal number of processes are required to roll back, and the time needed to revert to normal operation is found to be minimal, thus contributing to the real-time requirements for such systems. Furthermore, the stable storage requirement needed to implement our recovery procedure is bounded and minimal. Proofs of correctness of our procedure are provided, in particular, the absence of orphan messages, message losses, and duplications is shown. An example illustrating our recovery procedure is also provided.