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