基于检测点设置依赖图和属性表的卷回恢复算法

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

为了解决检测点设置过程中的 Dom ino效应问题及卷回恢复过程中的活锁问题 ,并最大限度地减小时间开销 ,提出了基于检测点设置依赖图和属性表的卷回恢复算法 .同以前的算法相比较 ,该算法一方面节省了用于进程之间同步的时间开销 ,另一方面检测点设置及卷回过程中只涉及少量的相关进程 .

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.