An efficient checkpointing protocol for the minimal characterization of operational rollback-dependency trackability

A checkpointing protocol that enforces rollback-dependency trackability (RDT) during the progress of a distributed computation must induce processes to take forced checkpoints to avoid the formation of nontrackable rollback dependencies. A protocol based on the minimal characterization of RDT tests only the smallest set of nontrackable dependencies. The literature indicated that this approach would require the processes to maintain and propagate O(n²) control information, where n is the number of processes in the computation. In this paper, we present a protocol that implements this approach using only O(n) control information.