Consistency issues in distributed checkpoints

A global checkpoint is a set of local checkpoints, one per process. The tra ditional consistency criterion for global checkpoints states that a global checkpoint is consistent if it does not include messages received and not s ent. This paper investigates other consistency criteria, transitlessness, a nd strong consistency. A global checkpoint is transitless if it does not ex hibit messages sent and nor received. Transitlessness can be seen as a dual of traditional consistency. Strong consistency is the addition of transitl essness to traditional consistency. The main result of this paper is a stat ement of the necessary and sufficient condition answering the following que stion: "Given an arbitrary set of local checkpoints, can this set be extend ed to a global checkpoint that satisfies P-m (where LP is traditional consi stency, transitlessness, or strong consistency). From a practical point of view, this condition, when applied to transitlessness, is particularly inte resting as it helps characterize which messages do not need to be recorded by checkpointing protocols.