On the memory overhead of distributed snapshots

This paper shows that the memory overhead of distributed snapshots is unbounded. Several techniques are suggested for bounding it: bounded memory-overhead versions of distributed snapshots for specific problems, like termination detection and deadlock detection; use of alternative protocols; or use of synchronizers or schedulers in order to limit the photographed protocol to executions whose distributed snapshot requires bounded memory. Each solution is discussed in detail, and its memory overhead is analyzed. (C) 1999 John Wiley & Sons, Inc. Networks 34: 11-17, 1999.