#Number
TR-PDS-2001-004
#Title
Computation Slicing: Techniques and Theory
#Author
Neeraj Mittal
Vijay K. Garg
#Abstract
We generalize the notion of slice introduced in our earlier
paper. A slice of a distributed computation with respect to a global
predicate is the smallest computation that contains all consistent
cuts of the original computation that satisfy the predicate. We prove
that slice exists for all global predicates. We also establish that it
is, in general, NP-complete to compute the slice. Optimal algorithms
to compute slices for special cases of predicates are provided.
Furthermore, we present an efficient algorithm to graft two slices,
that is, given two slices, either compute the smallest slice that
contains all consistent cuts that are common to both slices or compute
the smallest slice that contains all consistent cuts that belong to at
least one of the slices. We give application of slicing in general
and grafting in particular to global property evaluation of
distributed programs. Finally, we show that the results pertaining to
consistent global checkpoints can be derived as special cases of
computation slicing.
#Bib
@techreport{TR01004,
author = "Neeraj Mittal and Vijay K. Garg",
title = "Computation Slicing: Techniques and Theory",
instituition = "The University of Texas at Austin",
year = "2001",
number = "TR-PDS-2001-004",
note = "available via ftp or WWW at maple.ece.utexas.edu
as technical report TR-PDS-2001-004"
}