#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"
}