Tech Report CS-93-32

Necessary and Sufficient Conditions for Consistent Global Snapshots

Robert H.B. Netzer and Jian Xu

July 1993

Abstract:

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)