Finding satisfying global states: all for one and one for all

摘要

Summary form only given. 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. 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|) 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 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. We also give an online algorithm for computing the slice for a predicate that can be detected efficiently. The amortized time-complexity of the algorithm is O(n(c + n)) times the time-complexity of the detection algorithm, where c is the average concurrency in the computation.