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