Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest sub-computation — with the least number of consistent cuts — that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b The time-complexity of the (derived) slicing algorithm is 0(n|E|) times the time-complexity of the detection algorithm, where n is the number of processes and E is the set of events. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the general predicate detection problem.

Slicing algorithms described in our earlier papers are all off-line in nature. In this paper, we also give an on-line algorithm for computing the slice for a predicate that can be detected efficiently. The amortized time-complexity of the algorithm is 0(n(c+n)) times the time-complexity of the detection algorithm, where c is the average concurrency in the computation.