Effective and concurrent checkpointing and recovery in distributed systems

摘要

The paper presents an effective application-transparent checkpointing/rollback scheme for multiple processes that communicate via message passing in a distributed system. The authors first propose a checkpointing scheme that uses the unforced checkpointing strategy and dynamically varies checkpoint intervals with respect to the frequency of message sending to reduce process rollback propagation. Additional forced checkpoints are taken only to achieve checkpoint consistency among processes and to avoid the domino effect. The authors then discuss both global rollback and minimal rollback approaches, and incorporate them into the proposed checkpointing scheme. The combined checkpointing/rollback scheme can handle out-of-order messages, achieve high concurrency during checkpointing/rollback operations, and allow multiple invocations of checkpointing/rollback instances. To reduce the space overhead a global recovery line determination approach to purge the checkpoints to which processes shall never is proposed. Experiences with event driven simulation indicate that the proposed scheme can effectively reduce rollback propagation, while incurring little control message overhead and maintaining at any time only a few checkpoints at each process.