Subject: bibliography for global predicate detection ...

From: [email-masked] (Kapil Gupta)
Date: Tue, 7 May 1996 19:11:15 -0500

Hi Dr. Garg,
        Thanks for letting me borrow those two papers. They were a
big help. I am attaching a postscript version of the bibliography
below.

Kapil

-------------------------------------------------------------------
\documentstyle[11pt]{article}
\bibliographystyle{plain}
\thispagestyle{empty}

\title{Annotated Bibliography on Global Predicate Detection}
\author{Kapil Gupta}

\begin{document}
\maketitle

\section*
{\bf Chandy and Lamport 1985}
K.M. Chandy and L. Lamport. Distributed snapshots: Determining global states
of distributed systems. {\it ACM Transactions on Computer Science}, Vol 3, 
No. 1, 63-75, February 1985. \\
\\
Chandy and Lamport were the first to give an algorithm for computation of
a meaningful global snapshot. This paper presents the classic ``distributed
snapshot'' algorithm which is intended to provide a general purpose
framework which can be adapted to specific implementation requirements.
However the approach works only for stable predicates and does not give
any indication as to when the snapshot needs to be taken.

\section*
{\bf Spezialetti and Kearns 1986}
M. Spezialetti and P. Kearns. Efficient Distributed Snapshots. In {\it 
Proceedings of the $6^{th}$ International Conference on Distributed Computing
Systems}, 382-388, 1986. \\
\\
This paper presents efficient algorithms to disseminate a global snapshot to
processes initiating the snapshot computation. The authors have modified the
algorithm proposed by Chandy and Lamport so that the earlier phase can provide
useful information to the later phase which may be utilized to advantage by the
later phase. This modified algorithm is more efficient for repeated snapshots
and is thus suitable for stable predicate detection. 

\section*
{\bf Miller and Choi 1988}
B.P. Miller and J. Choi. Breakpoints and halting in distributed programs. In
{\it Proceedings of the $8^{th}$ IEEE International Conference on Distributed
Computing Systems}, San Jose, 316-323, July 1988. \\
\\
This paper discusses detection of linked predicates, basically a causal
sequence of local states verifying some predicates. This was the first paper
describing such a behavioral pattern in the system. The algorithm proposed
does not require building the lattice or using a centralized manager and uses
a simple piggy-backing technique to ensure consistency in the detection.

\section*
{\bf Spezialetti and Kearns 1989}
M. Spezialetti and P. Kearns. Simultaneous Regions: A Framework for the 
Consistent Monitoring of Distributed Systems. In {\it Proceedings of the 
$9^{th}$ International Conference on Distributed Computing Systems}, Newport 
Beach, 61-68, July 1989. \\
\\
In this paper the authors have define a notion of simultaneity which is used
to combine local states into a globally consistent state. Predefined predicates
are evaluated for each global state, and if the predicate holds, a so-called
{\it global event occurrence} is recognized. However there is a basic flaw 
in their definition of simultaneity, due to which the algorithm may fail to
detect a global event occurrence.

\section*
{\bf Fowler and Zwaenepoal 1990}
J. Fowler and W. Zwaenepoal. Causal Distributed Breakpoints. In {\it 
Proceedings of the $10^{th}$ International Conference on Distributed Computing 
Systems}, Paris, France, 134-141, May 1990. \\
\\
This paper proposes an algorithm to compute {\it causal distributed 
breakpoint}. When one process of a distributed computation is halted at a
breakpoint, the causal distributed breakpoint shows the other processes in
the computation in their earliest state that reflects all events that
happened before the breakpoint. 

\section*
{\bf Cooper and Marzullo 1991}
R. Cooper and K. Marzullo. Consistent detection of global predicates. In
{\it Proceedings of the ACM/ONR Workshop on Parallel and Distributed 
Debugging}, Santa Cruz, CA, 163-173, May 1991. \\
\\
Cooper and Marzullo were the first to use the construction of the lattice of 
global states to detect arbitrary global predicates. This approach allows the 
user to detect {\it definitely}: q and {\it possibly}: q where q is any 
predicate defined on a single global state. This approach works even for 
unstable predicates. However given $n$ processes each with $m$ ``relevant'' 
local states, their off-line algorithm requires exploring $O(m^n)$ possible 
global states in the worst case.  

\section*
{\bf Garg and Waldecker 1992}
V.K. Garg and B. Waldecker, Detection of Unstable Predicates in Distributed 
Programs.  In {\it Proceedings of the 12th Conference on the Foundations of Software 
Technology \& Theoretical Computer Science}, New Delhi, India, Springer-Verlag, 
253-264, 1992. \\
\\
This paper discusses detection of strong global predicates in a distributed
system, where a strong predicate is defined as one which is definitely 
true in all possible executions. The authors present algorithms to detect 
strong linked predicates (a chain of predicates linked by a causal relationship) as well as strong conjunctive predicates (predicates formed by conjunction of
local predicates).

\section*
{\bf Venkatesan and Dathan 1992}
S. Venkatesan and B. Dathan. Testing and debugging distributed programs
using global predicates. In {\it Thirtieth Annual Allerton Conference
on Communication, Control and Computing}, Allerton, Illinois, 137-146,
October 1992. \\
\\
This paper discusses completely distributed algorithms for off-line
evaluation of conjunctive global predicates. The algorithm proposed in
this paper has the same time complexity as the on-line algorithm proposed by 
Garg and Waldecker. The algorithm deals with predicates which are possibly 
true as well as those which are definitely true in the execution.

\section*
{\bf Hurfin, Plouzeau and Raynal 1993}
M. Hurfin, N. Plouzeau and M. Raynal. Detecting atomic sequences of
predicates in distributed computations. In {\it Proceedings of the
ACM/ONR Workshop on Parallel and Distributed Debugging}, San Diego, CA,
32-42, Dec 1993. \\
\\
This paper discusses detection of a particular class of behavioral patterns
in a distributed system. The authors have generalized the {\it linked 
predicate} introduced by Miller and Choi to a more general {\it atomic sequence
of predicates} in which some events can be forbidden between each pair of
consecutive relevant events. The algorithm proposed uses a message piggy-backing technique to ensure consistency of the detection.

\section*
{\bf Tomlinson and Garg 1993}
A.I. Tomlinson and V.K. Garg. Detecting Relational Global Predicates in 
Distributed Systems.  In {\it Proceedings of ACM/ONR Workshop on Parallel and 
Distributed Debugging}, San Diego, California, 21-31, May 1993. \\
\\
In this paper the authors discuss how to efficiently monitor a program to 
determine if
there exists a global state in which the sum $X_1 + X_2 + \ldots + X_N$
exceeds some constant $K$, where e$X_i$ is defined in process $i$. Thus this
paper extends the class of global functions which can be efficiently 
detected in a distributed program.

\section*
{\bf Babao\u{g}lu and Marzullo 1993}
\"{O}. Babao\u{g}lu and K. Marzullo. Consistent global states of distributed 
systems: Fundamental concepts and mechanisms. In Sape Mullender, editor, {\it 
Distributed Systems}, chapter 5, 97-145. Addison Wesley, $2^{nd}$ ed., 1993. \\
\\
This paper is a survey of the concepts and mechanisms useful in
understanding the problem of ``Global Predicate Evaluation''. The
authors discuss  distributed deadlock detection and distributed debugging
as examples where the above concepts can be applied.

\section*
{\bf Garg and Waldecker 1994}
V.K. Garg and B. Waldecker. Detection of Weak Unstable Predicates in 
Distributed Programs. {\it IEEE Transactions on Parallel and Distributed 
Systems}, Vol 5, No. 3, 299-307, March 1994. \\
\\
This paper discusses detection of weak global predicates formed by  
conjunction of local predicates. The author defines a weak predicate to
be one which is possibly true in the system. The algorithm proposed exploits
the structure of the predicate and has message complexity bounded by the number
of messages in the system.

\section*
{\bf Tomlinson and Garg 1994}
A. I. Tomlinson and V. K. Garg. Maintenance of Global Assertions in 
Distributed Systems. In {\it Proceedings of the International Conference on 
Computer Science and Education}, Bangalore, India, Tata McGraw-Hill Publishing 
Company Limited, 257-272, June 1994. \\
\\
This paper develops a method for maintaining global assertions in a 
distributed system. The global assertion has the form $(X_1^1X_2^1 \ldots 
X_{N_1}^1) + \ldots + (X_1^MX_2^M \ldots X_{N_M}^M) \geq K$, where $X_i^j$ is
a variable which is local to one process and $K$ is a constant. This form is 
more general than the summation form considered earlier by the same authors,
and solves many classical synchronization problems including mutual-exclusion. 

\section*
{\bf Jard, J\'{e}ron, Jourdan and Rampon 1994}
C. Jard, T J\'{e}ron, G.V. Jourdan and J.X. Rampon. A General Approach to
Trace-Checking in Distributed Computing Systems. In {\it Proceedings of 
the $14^{th}$ International Conference on Distributed Computing Systems}, 
Poznan, Poland, 396-403, June 1994. \\
\\
This paper suggests that a relevant model for on-line
detection of properties is the partial order of message causality and the
associated state graph. The authors discuss two different codings of the causal
poset, vector clocks and direct dependency clocks, and give algorithms for
on-line construction of the covering digraphs. 

\section*
{\bf Schwartz and Mattern 1994}
R. Schwartz and F. Mattern. Detecting causal relationships in distributed
computations: In search of the holy grail. {\it Distributed Computing},
vol 7, No. 3, 149-174, 1994 \\
\\
This paper surveys the work done on the detection of causal relationships
in distributed computing.  The relative merits and limitations of the different 
approaches are discussed, and their general feasibility is analyzed. The
paper also discusses some fundamental problems in the particular research
area including lack of a well established formalism leading to substantially
different system models in the literature. It is a very comprehensive survey
paper and a very valuable source of information for understanding this topic.

\section*
{\bf Fromentin, Raynal, Garg and Tomlinson 1994}
E. Fromentin, M. Raynal,  V.K. Garg and A.I. Tomlinson. On The Fly 
Testing of Regular Patterns in distributed computations. In {\it Proceedings
of the $23^{rd}$ International Conference on Parallel Processing}, St. Charles, 
IL, 73-76, August 1994. \\
\\
This paper discusses the detection of regular patterns in a distributed
system. The author defines regular patterns as causal sequences of relevant
events defined by a finite state automaton and is therefore more generalized
than {\it linked predicates} or {\it atomic sequences}. The detection algorithm
is on-line and does not involve the construction of lattice. 

\section*{Garg, Chase, Mitchell and Kilgore 1995}
{\bf }
V. K. Garg, C. Chase, J. R. Mitchell and R. Kilgore. Detecting conjunctive 
Channel Predicates in a Distributed Programming Environment. In {\it  $28^{th}$ 
Hawaii International Conference on System Sciences}, 232-241, January 1995.\\
\\
This paper discusses detection of global predicates in a distributed
program  which might also include the state of channels. The authors have 
introduced the notion of monotonicity for channel predicates (the predicate
is guaranteed to be false in one direction) which allows for efficient 
detection of the predicates; the message complexity is bounded by the number
of messages used by the program.

\section*{Babao\u{g}lu, Fromentin and Raynal 1995}
{\bf }
\"{O}. Babao\u{g}lu, E. Fromentin and M. Raynal. A Unified Framework for the 
Specification and Run-time Detection of Dynamic Properties in Distributed
Computations. Research Report 967, IRISA, Campus de Beaulieu 35042 Rennes 
Cedex, France, February 1995. \\
\\
This report attempts to unify a large body of work on distributed debugging
and property detection by formulating it as a language recognition problem.
The authors presents a general framework to express a large class of properties
for distributed computations as languages over alphabets of predicates. Some
examples of properties that can be expressed as regular grammar through finite 
automata have been included.

\section*{J\'{e}gou, Medina and Nourine 1995}
{\bf }
R. J\'{e}gou, R. Medina and L. Nourine. Linear space algorithm for on-line
detection of global predicates. In {\it Proceedings of the International
Workshop on Structures in Concurrency Theory (STRICT '95)}, Berlin, Germany,
175-189, 1995. \\
\\
This paper proposes an algorithm for on-line detection of an arbitrary global 
predicate possibly true in a distributed system. This is the first on-line 
algorithm which uses space linear in the total number of global states in the  
causality order. The algorithm presented is based on a particular spanning 
tree of the ideal lattice.

\section*{Stoller and Schneider 1995}
{\bf }
S.D. Stoller and F.B. Schneider. Faster Possibility Detection by Combining
Two Approaches. In {\it Distributed algorithms : 9th international workshop, 
WDAG '95}, Le-Mont-Saint-Michel, France, 318-332, September 1995. \\
\\
This paper presents a new algorithm to detect if an arbitrary global predicate
is possibly true in a distributed system. The algorithm is a generalization
of the one proposed by Garg and Waldecker, which only works for boolean 
combinations of local predicates, and is a significant improvement over the
existing algorithms which construct the entire lattice to detect the predicate.

\section*{Hurfin, Mizuno, Raynal and Singhal 1995}
{\bf }
M. Hurfin, M. Mizuno, M. Raynal and M. Singhal. Efficient Distributed Detection
of Conjunction of Local Predicates. Research Report 967, IRISA, Campus de
Beaulieu 35042 Rennes Cedex, France, November 1995. \\
\\
This paper presents efficient distributed algorithms to detect conjunctive
form of global predicates in a distributed system. In the proposed algorithm
the worst case volume of control information is identical to that
of the distributed algorithm proposed by Garg and Chase, however all or most
of the control information is piggy-backed on computational messages.

\end{document}