An efficient incremental algorithm for identifying consistent checkpoint

Abstract

In a distributed system, identifying consistent check points is essential for error recovery and debugging. In this paper, me design an efficient incremental algorithm capable of identifying all the consistent and removable checkpoints each time a new checkpoint is reported. By doing so, the required memory space can be minimized by removing those removables. While minimizing the memory space, the algorithm requires only O(p(2)M) time in total, where p is the number of processes and M is the number of checkpoints.