Consistent Checkpointing in Message Passing Distributed Systems

A global checkpoint of a distributed computation is a a set of local checkpoints (local states), one per process. Determining consistent global checkpoints is an important problem for many distributed applications (e.g. fault-tolerance, distributed debugging, properties detection, etc). This paper focuses on such determinations. A precedence relation on checkpoint intervals (such intervals are sets of events produced by processes between two successive local checkpoints) is introduced and analyzed. It is shown that a local checkpoint is useless (i.e. it cannot participate in any consistent global checkpoint) iff some pattern occurs in this precedence relation. Then an adaptive checkpointing algorithm is introduced. This algorithm, assuming processes take local checkpoints independently, requires them to take (as few as possible) additional checkpoints in order that none of local checkpoints be useless. It is based on the prevention of the previously mentioned pattern. In some sense, this algorithm combines..