#Number
TR-PDS-1994-003

#Title
Distributed Algorithms for Detecting Conjunctive Predicates

#Author
Vijay K. Garg
Craig Chase

#Abstract
This paper discusses efficient distributed detection of global
conjunctive predicates in a distributed program.  Previous work in
detection of such predicates is based on a centralized checker
process.  The checker process 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 in the system.  In this paper, we discuss
token-based algorithms which distribute the computation and space
requirements of the detection procedure.  The total number of
messages required by the system is the same as in the centralized
algorithm, $O(mn)$.  We also establish $\Omega(mn)$ as a lower bound
on the time complexity for predicate detection.


#Bib
@TechReport{,
  author = 	 "V.K. Garg and C. Chase",
  title = 	 "Distributed Algorithms for Detecting
		  Conjunctive Predicates",
  institution =  "Parallel and Distributed Systems Laboratory, The
		  University of Texas at Austin", 
  year =	 1994,
  number =	 "TR-PDS-1994-003",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu"
}