INCREMENTAL TRANSITIVE DEPENDENCY TRACKING IN DISTRIBUTED COMPUTATIONS
Claude Jard, Guy-Vincent Jourdan · Parallel Processing Letters · 1996
The notion of causal dependency between events in distributed systems plays a central role in reasoning about distributed program behaviours [14]. Different techniques have been designed to track these dependencies during execution. We suggest a new incremental transitive dependency tracking technique. Once the transitive dependencies are recorded for an observable event, the dependency tracking cost can be reduced by propagating only future dependencies beyond that event. Furthermore, in contrast with the direct dependency tracking technique already proposed in the literature, our technique allows to compute the dependencies among an arbitrary subset of observable events. This gives an interesting filtering capability.