Using directed graphs to describe entity dependency in stable distributed persistent stores

In a persistent object store, the acts of modifying data and reading modified data result in the creation of dependencies between the modifying process and the data. Dependencies may be represented using sets, and over time these may grow to encompass many objects and processes. Checkpoint and roll-back operations must propagate to all elements in such a set. This paper presents a new notation for representing dependencies, and shows that differentiating between the dependencies created by modifying data and reading modified data reduces the extent of propagation of checkpoint and roll-back operations.