Tech Report CS-93-32

Necessary and Sufficient Conditions for Consistent Global Snapshots

Robert H.B. Netzer and Jian Xu

July 1993


Consistent global snapshots are important in many distributed applications. We prove the exact conditions for an arbitrary checkpoint, or a set of checkpoints, to belong to a consistent global snapshot, a previously open problem. To describe the conditions, we introduce a generalization of Lamport's happened-before relation called a zigzag path.

(complete text in pdf or gzipped postscript)