ROLLBACK RECOVERY ALGORITHM BASED ON THE CHECKPOINT DEPENDENCY GRAPH AND THE PROPERTY TABLE

To solve the problem of domino effect and livelock during the checkpoint and error recovery procedure and to decrease the cost of the runtime, a distributed algorithm （named rollback\|recovery algorithm） to create consistent checkpoints based on the checkpointing dependency graph and the property table is proposed in this paper. Conpared with the previous algorithms, this algorithm reduces synchronization overhead for a process to take a checkpoint. A minimal number of additional processes are forced to take checkpoints or roll back with it. The correctness of the algorithm is proved.