Communication-based prevention of useless checkpoints in distributed computations

A useless checkpoint is a local checkpoint that cannot be part of a consist ent global checkpoint. This paper addresses the following problem. Given a set of processes that take (basic) local checkpoints in an independent and unknown way, the problem is to design communication-induced checkpointing p rotocols that direct processes to take additional local (forced) checkpoint s to ensure no local checkpoint is useless. The paper first proves two properties related to integer timestamps which a re associated with each local checkpoint. The first property is a necessary and sufficient condition that these timestamps must satisfy for no checkpo int to be useless. The second property provides an easy timestamp-based det ermination of consistent global checkpoints. Then, a general communication- induced checkpointing protocol is proposed. This protocol, derived from the two previous properties, actually defines a family of timestamp-based comm unication-induced checkpointing protocols. It is shown that several existin g checkpointing protocols for the same problem are particular instances of the general protocol. The design of this general protocol is motivated by t he use of communication-induced checkpointing protocols in "consistent glob al checkpoint"-based distributed applications such as the detection of stab le or unstable properties and the determination of distributed breakpoints.