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 di erences, a new algorithm for fast incremental checkpointing. Compressed di erences 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 di erences, called standard and online compressed di erences. 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 di erences almost invariably improve the performance of both sequential and incremental checkpointing.