``Compressed Differences: An Algorithm for Fast Incremental Checkpointing''

James S. Plank, Jian Xu and Rob Netzer

Technical Report CS-95-302, University of Tennessee, August, 1995.

This paper was never published in a conference or journal -- pity, because it's a pretty good paper...

Available via anonymous ftp to cs.utk.edu in pub/plank/papers/CS-95-302.ps and pub/plank/papers/CS-95-302.pdf.


The overhead of saving checkpoints to stable storage is the dominant performance cost in checkpointing systems. In this paper, we present a complete study of compressed differences, a new algorithm for fast incremental checkpointing. Compressed differences reduce the overhead of checkpointing by saving only the words that have changed in the current checkpointing interval while monitoring those changes using page protection.

We describe two checkpointing algorithms based on compressed differences, called standard and online compressed differences. These algorithms are analyzed in detail to determine the conditions that are necessary for them to improve the performance of checkpointing. We then present results of implementing these algorithms in a uniprocessor checkpointing system. These results both corroborate the analysis and show that in this environment, standard compressed differences almost invariably improve the performance of both sequential and incremental checkpointing.

Postscript of the paper

PDF of the paper

Citation Information