#Number
TR-PDS-1995-008

#Title
Distributed Algorithms for Detecting Conjunctive Predicates



#Author
Vijay K. Garg and Craig M. Chase

#Abstract
  This paper discusses efficient distributed detection of global
  conjunctive predicates in a distributed program.  Our methods
  correctly detect the first consistent cut in which the predicate is
  true, even if the predicate is unstable.  Previous work in
  detection of such predicates is based on a centralized checker
  process.  

  In this paper, we introduce algorithms which distribute
  the computation and space requirements of the detection procedure.
  Two algorithms are presented.  The first algorithm requires
  O(n**2m) time and space where m is the number of messages sent by
  any process and n is the number of processes over which the
  predicate is defined.  This algorithm has identical time complexity
  to the original centralized algorithm.  However computation, space
  and message requirements are distributed evenly over the n processes.
  The second algorithm requires O(Nm) total work, where N is the
  total number of processes in the system.  The relative values of n
  and N determine which algorithm is more efficient for a specific
  application.  

  Parallelism can be introduced into either distributed algorithm,
  reducing the average case time complexity.  We show that the
  worst-case time complexity can not be improved beyond O(mn) with
  any on-line detection algorithm.

	
#Bib
  author =       "Vijay K. Garg and Craig M. Chase",
  title =        "Distributed Algorithms for Detecting Conjunctive
                  Predicates",
  OPTpages =     "",
  booktitle = "International Conference on Distributed Computing
                  Systems",
  year =      "1995",
  address =   "Vancouver, BC, Canada",
  month =     jun,
  note =      "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1995-008"
}