#Number
TR-PDS-1995-004

#Title
On Techniques and their Limitations for the Global Predicate Detection
Problem in Distributed Systems 

#Author
Craig M. Chase and Vijay K. Garg


#Abstract
  We show that the problem of predicate detection in distributed
  systems is NP-complete.  We introduce a class of predicates, 
  linear predicates, such that for any linear predicate B there
  exists an efficient detection of the least cut satisfying B.  We
  show that the least cut may not even exist if the predicate is not
  linear.  The dual of linearity is post-linearity.  These
  properties generalize several known properties of distributed
  systems, such as the set of consistent cuts forms a lattice, and the
  WCP and GCP predicate dectection results given in earlier work.

  We define a more general class of predicates, semi-linear
  predicates, for which efficient algorithms are known to detect 
  whether a predicate has occurred during an execution of a 
  distributed program.  However, these methods may not identify
  the least such cut.  Any stable predicate is an example of a
  semi-linear predicate.  In addition, we show that certain unstable
  predicates can also be semi-linear, such as mutual exclusion
  violation. 

  Finally, we show application of max-flow to the predicate detection
  problem.  We give a simple transformation of the traditional poset
  representation of a distributed execution into a flow graph.
  We show that computing the max-flow of this graph is equivalent to
  identifying a consistent cut which minimizes the sum of a set of
  distributed variables.  This result solves a previously open problem
  in predicate detection, establishing the existance of an efficient
  algorithm to detect predicates of the form x1 + x2 ... + xN < C
  where the xi are variables on different processes, C is some
  constant, and N is larger than 2.   

	
#Bib
@TechReport{CG95,
  author =       "Craig M. Chase and Vijay K. Garg",
  title =        "On Techniques and their Limitations for the Global
                  Predicate Detection Problem in Distributed Systems",
  institution =  "Parallel and Distributed Systems Laboratory, ECE
                  Dept. University of Texas at Austin",
  year =         "1995",
  number =    "TR-PDS-1995-004",
  note =      "submitted to the 1995 conference on Principles of
                  Distributed Computing",
  note =      "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1995-004",
}