Crash recovery with little overhead

Recovering from processor failures in distributed sys-tems is an important problem in the design and development of reliable systems. Several solutions to this problem have been presented in the literature. Most of them recover from failures by storing sufficient extra information in stable storage and using this information when there are failures. In this paper, we present two solutions to this problem which involve very little overhead. Without appending any information to the messages of the application pro-gram, we show that it is possible to recover from failures using O(IVIIEI) messages where IVI is the number of processors and IEl is the number of com-munication links in the system. The second algorithm can be used to recover from processor failures without forcing non-faulty processors to roll back under certain conditions. With a small modification, the second algorithm can also be used to recover from processor failures even if no stable storage is avail-able. 1