#Number
TR-PDS-1994-002

#Title
Detecting Conjunctive Channel Predicates in a Distributed
Programming Environment

#Author
Vijay K. Garg
Craig Chase
J. Roger Mitchell
Richard Kilgore

#Abstract
This paper discusses efficient detection of global predicates
in a distributed program.  Previous work in efficient detection of
global predicates was restricted to predicates that could be
specified as a boolean formula of local predicates.  Many properties
in distributed systems, however, use the state of channels. In this
paper, we introduce the concept of a channel predicate and provide
an efficient algorithm to detect any boolean formula of local and
channel predicates.  We define a property called monotonicity for
channel predicates.  Monotonicity is crucial for efficient detection
of global predicates.  We show that many problems studied earlier such
as detection of termination and computation of global virtual time
are special cases of the problem considered in this paper.  The
message complexity of our algorithm is bounded by the number of
messages used by the program.  The main application of our results
are in debugging and testing of distributed programs. Our algorithms
have been incorporated in a distributed programming environment
which runs on a network of IBM RS/6000 Workstations under AIX with
the PVM environment.

#Bib
@TechReport{,
  author = 	 "V.K. Garg and C. Chase and 
		  J.R Mitchell and R. Kilgore",
  title = 	 "Detecting Conjunctive Channel Predicates 
		  in a Distributed Programming Environment",
  institution =  "Parallel and Distributed Systems Laboratory, The
		  University of Texas at Austin", 
  year =	 1994,
  number =	 "TR-PDS-1994-002",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu"
}