Finding a recovery line in uncoordinated checkpointing

In distributed systems running uncoordinated checkpointing schemes, a process should maintain several generations of local checkpoints to improve dependability, because a global checkpoint, which is a set of local checkpoints, is not always consistent. In this paper, we present an algorithm for finding a recovery line, where a given checkpoint is the earliest, in uncoordinated checkpointing schemes. Numerical examples of probability for the existence of a recovery line calculated with the proposed algorithm are also presented.