#Number
TR-PDS-1994-012

#Title
Detecting Relational Global Predicates in Distributed Systems

#Author
Alexander I. Tomlinson
Vijay K. Garg 


#Abstract
This paper defines relational global predicates and presents
efficient algorithms to detect them in a distributed program
which uses unordered asynchronous messages for inter-process
communication.  We use relational global predicates of the
form $(x0 + x1 < C)$ where $x0$ and $x1$ are integer values at
processes $P0$ and $P1$ in a system of $N$ processes.  We
present a fully decentralized algorithm that runs concurrently
with the target program, uses constant size message tags (four
integers), and generates one debug message for each message
received by $P0$ and $P1$.  We also describe a centralized
algorithm that can be used as a checker process which runs
concurrently with the target program, or after the target
program terminates.  We generalize our results to an algebra
$(D,\%,*)$ where $\%$ and $*$ are binary operators in domain
$D$, $\%$ is commutative, associative and idempotent, and $*$
distributes over $\%$.  In this algebra we can calculate value
of the expression $(v1\:\%\:v2\:\% ... \%\:vn)$ where $\{
v1,v2,... vn \}$ is the set which contains the value of
$x0*x1$ in each consistent cut.  For example if $(D,\%,*) =
(\mbox{Integers}, \min,+)$ then we could calculate the minimum
value of $x0+x1$ over all consistent cuts.  This
generalization opens up many useful variants of our algorithm,
including detection of weak conjunctive boolean predicates.



#Bib
@InProceedings{,
  author = 	 "Alexander I. Tomlinson and Vijay K. Garg",
  title = 	 "Detecting Relational Global Predicates in
		  Distributed Systems", 
  pages =	 "21--31",
  booktitle =	 "Proceedings of ACM/ONR Workshop on Parallel and
		  Distributed Debugging",
  year =	 1993,
  organization = "ACM",
  address =	 "San Diego, California",
  month =	 "May",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1994-012"
}