A Causal Checkpointing Algorithm for Mobile Computing Environments

摘要

Checkpointing algorithms suitable for mobile computing environments should be economical in terms of storage and energy consumption, and they should be able to handle that at starting time not all processes are known which are to be involved in the checkpointing. We propose such an algorithm by generalizing Chandy/Lamport's snapshot algorithm in two ways: processes are given a certain autonomy when to take their local checkpoints, and processes send checkpoint requests only to processes they knowingly depend on. As, our algorithm comprises the so-called phase 1 of coordinated checkpointing, only, which -under reasonable progress assumptions - ensures that all the local checkpoints will be taken. We present the algorithm in terms of its operational semantics over which we prove the consistency of the calculated snapshot.