Solving Computation Slicing Using Predicate Detection

摘要

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 subcomputation--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 O(n|E|T), where n is the number of processes and E is the set of events, and O(T) is the time-complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the general predicate detection problem in many cases.Slicing algorithms described in our earlier papers are all off-line in nature. In this paper, we also present two on-line algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time-complexity is O(n(c + n)T), where c is the average concurrency in the computation and O(T) is the time-complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time-complexity is only O(n2).