Rollback-dependency trackability

Abstract

When we consider an asynchronous distributed computation on which local checkpoints have been defined (namely, a communication and checkpoint pattern -in brief, CCP), two types of dependencies between its local checkpoints can be observed. The first type is due to causal sequences of messages that establish on-line trackable dependencies. The second type is due to noncausal sequences of messages (called Z-paths) that establish "hidden" dependencies between local checkpoints (a dependency is "hidden" if it can not be tracked online). The Rollback Dependency Trackability (RDT) property, defined by Y.-M. Wang, has been introduced to study CCPs. A CCP satisfies the RDT property if every pair of local checkpoints that are connected by a "hidden" dependency are also connected by a causal sequence of messages. The RDT property has a great interest: CCPs that satisfy this property allow relatively simple solutions to a lot of practical problems. This paper first introduces the notion of RDT-compliant property. In a given CCP, an X-path is a Z-path that satisfies a property X. The property X is RDT-compliant if every CCP without X-paths satisfies the RDT property. Then, the paper presents a particular RDT-compliant property. This property enjoys several very interesting features. (1) It is "visible" (i.e., it can be tested on-line).