Computation Slicing

A computation slice with respect to a predicate B is a subcomputation that includes all consistent global states that satisfy B. Computation slicing has two main applications. First, it allows one to narrow down the state space. For example, suppose you are looking for a state satisfying B1 and B2. Assume that B2 is a complex predicate and the only way to search for it is to examine all global states. By using computation slicing, we can compute the slice for B1 and narrow our search to oly those states that satisfy B1. The second application of slicing is in detecting temporal logic formulas. A slice is used to represent the set of global states satisfying the intermediate subformulas. The notion of slicing was first introduced in

  • Vijay K. Garg and Neeraj Mittal,On Slicing a Distributed Computation,Proc. IEEE International Conference on Distributed Computing Systems, Phoenix, May 2001 (nominated for the best paper award), pp. 322 - 329 .Abstract ...........Postscript

    • A more general definition and techniques to compute the slice is available as

  • Neeraj Mittal and Vijay K. Garg, Techniques and Applications of Computation Slicing Distributed Computing link to Springer

    pdf

    • The above paper provides an algorithm to compute slice for any meet-closed predicate. The following paper shows the surprising result that any predicate that can be efficiently detected can also be used for slicing. This result enables efficient slicing for bounded-sum predicates.

  • Neeraj Mittal, Alper Sen, Vijay K. Garg, and Ranganath Atreya, Finding Satisfying Global States: All for One and One for All, In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), April 2004. ........... Postscript ........... pdf

    • Since many large combinatorial state spaces can be viewed as the set of down-sets of posets, there are many combinatorial applications of slicing. Some applicaions are provided in

  • Vijay K. Garg, Algorithmic Combinatorics based on Slicing Posets , accepted Theoretical Computer Science , ...pdf .