Systematic Analysis of Index-Based Checkpointing Algorithms using Simulation
Gustavo M. D. Vieira, Islene Calciolari Garcia, Luiz Eduardo Buzato · 2007
Abstract Index-based checkpointing allows the use of simple and efficient algorithms for dom-ino-effect free construction of recovery lines. In this paper, we use a simulation toolkit to analyze the behavior of index-based algorithms. We present a performance study ofthe well-known algorithm proposed by Briatico, Ciuffoletti, and Simoncini and explore the impact of some optimizations of this algorithm presented in the literature. Our resultsindicate that an expensive and complex optimization may not reduce the number of forced checkpoints in comparison to a simpler optimization. Keywords: distributed checkpointing, rollback recovery, logical clocks, simulation ofdistributed systems. 1 Introduction A checkpoint is a stable memory record of a process state. A consistent global checkpoint is aset of checkpoints, one per process, that could have been seen by an idealized observer external to the computation [3]. A recovery line is a consistent global checkpoint from which a dis-tributed computation can be restarted after a failure. Fault tolerance based on checkpoints and recovery lines can be divided into three autonomous activities. Checkpointing is concernedwith efficient protocols for the recording of checkpoints. Recovery deals with efficient protocols for constructing and rolling processes back to a recovery line [4]. Garbage collectionremoves from stable memory checkpoints that are no longer useful to rollback recovery [16].