Detection of Strong Unstable Predicates in Distributed Programs.
AbstractThis paper discusses detection of global predicates in a distributed program. A run of a distributed program results in a set of sequential traces, one for each process. These traces may be combined to form many global sequences consistent with the single run of the program. A strong global predicate is true in a run if it is true for all global sequences consistent with the run. We present algorithms which detect if the given strong global predicate became true in a run of a distributed program. Our algorithms can be executed on line as well as off line. Moreover, our algorithms do not assume that underlying channels satisfy FIFO ordering.
Introduction
Detection of global predicates is a fundamental problem in distributed computing. It arises
in the designing, debugging and testing of distributed programs. Global predicates can
be classified into two types - stable and unstable. A stable predicate is one which never
turns false once it becomes true. An unstable predicate is one without such a property.
Its value may alternate between true and false. Detection of stable predicates has been
addressed in the literature by means of global snapshots of a distributed computation
[ChaLam85, SpeKea86, Bouge87]. Any stable property can be detected by taking global
snapshots periodically. This approach does not work for an unstable predicate which may
turn true only between two snapshots and not at the time when the snapshot is taken. An
entirely different approach is required for such predicates [WalGar91, CooMar91, GarWal92,
SchMat92, GarWal94, BabMar93, TomGar93, HPR93].
We have earlier presented an approach to detect a class of unstable predicates called
predicates [GarWal94]. In this paper, we continue our investigation of detection for a
different class of unstable predicates. The reader is referred to [GarWal94] for a discussion of
related work and the background. Two types of predicates are discussed in this paper. The
first type, called strong linked predicates, refers to a causal sequence of local predicates. The
second type, called strong conjunctive predicates, correspond to existence of a global state
in which all local predicates are true simultaneously. We introduce the notion of overlapping
intervals which is used to detect predicates of this type. Cooper and Marzullo [CooMar91]
also describe strong predicate detection (they call such predicates definitely). However,
they deal with general predicates, i.e., they propose detection of definitely : p where p is any
predicate defined on a global state. In this paper, we have restricted p to conjunction of local
predicates. Detection of general predicates is intractable since it involves a combinatorial
This work was supported in part by the NSF Grant CCR 9110605, the Navy Grant N00039-91-C-0082,
a TRW faculty assistantship award, and IBM Agreement 153.
explosion of the state space. For example, the algorithm proposed by Cooper and Marzullo
[CooMar91] has complexity O(k n ) where k is the maximum number of events a monitored
process has executed and n is the number of processes. The fundamental difference between
our algorithm and their algorithm is that their algorithm explicitly checks all possible global
states, whereas our algorithm does not.
Spezialetti and Kearns [SpeKea89] also discuss a notion of simultaneity which, however,
is different from the one discussed in this paper. They use simultaneity in the sense of
a possible consistent global state. Their notion is closer to weak predicates discussed in
[GarWal94].
This paper is organized as follows: Section 2 presents our logic for specification of global
predicates in a distributed program. It describes the notion of a distributed run, a global
clock, a global sequence and the logic. Section 3 discusses detection of linked predicates.
Section 4 discusses strong conjunctive predicates. It gives necessary and sufficient conditions
for strong conjunctive predicates to hold. It also describes algorithms for detecting strong
conjunctive predicates. Section 5 presents techniques to decentralize these algorithms.
Our Model
We assume a loosely-coupled message-passing system without any shared memory or a global
clock. A distributed program consists of a set of n processes denoted by fP
communicating solely via asynchronous messages. We do not make any assumptions on the
ordering or reliability of messages.
A. Run
We will be concerned with a single run r of a distributed program. Each process P i in
that run generates an execution trace s i;0 s which is a finite sequence of local states
in the process P i . A run r is a vector of traces with r[i] as the trace of the process P i .
We define a relation locally precedes denoted by OE im between states in the trace of a single
process P i as follows: s OE im t if and only if s immediately precedes t in the trace r[i]. We
also say that t. We use OE for irreflexive transitive
closure and  for for reflexive transitive closure of OE im . States s and t in the traces r[i]
and r[j] respectively are defined to be related by ; if and only if a message is sent by P i
resulting in the state s which is received by P j resulting in the state t. Figure 1 illustrates
a run.
We also define a causally precedes relation as the transitive closure of union of OE im and
;. That is,
1.
2.
Our ! is similar to Lamport's happened-before relation [Lamp78] except that causally precedes
is defined between states rather than events. We say that s and t are concurrent
(denoted by sjjt) if :(s
pc,x 1,3 2,3
pc,y
y := y+3 receive(y) y:=2*y

Figure

1: An example of a run
We extend the run r to r 0 by adding artificial states ? i and ? i at the beginning and
the end of each trace r[i] respectively. The event at ? i (? i ) corresponds to the beginning
(termination) of the execution of P i . The addition of these artificial states model the fact
that processes begin their execution asynchronously. Thus, in absence of any synchronization
(external events) it may be possible that one process may have terminated while the
other one has yet to begin the execution. Let S i be the set of all states in the sequence r[i],
g. Our definitions imply that 8s 2 We define
i . We also use s:p to denote the process in whose trace s occurs.
That is,
B. Global Clock
A global clock C is a map from S 0 to N (the set of natural numbers) with the following
constraint:
We use C to denote the set of all global clocks which satisfy the above constraint. The
interpretation of C(s) for any s 2 S is that the process s:p enters the state s when the clock
value is C(s). Thus, it stays in the state s from time C(s) to C(s:next) \Gamma 1. This constraint
models the sequential nature of execution at each process and the physical requirement that
any message transmission requires a non-zero amount of time. From the definition of !, it
is equivalent to
The condition (CC) is widely used as the definition of a logical clock since its proposal by
Lamport[Lamp78]. It can be shown that the set C also satisfies the converse of (CC), i.e.,
The reader is referred to [GarWal94b] for the proof. This leads to the following pleasant
characterization of !:
Intuitively, the above formula says that s causally precedes t in a run r if and only if all
possible observers of the run agree that s happened before t.
C. Global Sequence
A global state is a vector of local states. This definition of global state is different from
that of Chandy and Lamport which includes states of channels. In our model, a channel
is just the set of all those messages that have been sent but not received yet. Since this
set can be deduced from all the local states, we do not require the state of channels to be
explicitly included in the global state. Given a run r, and a global clock C, seq(r; C) defines
a sequence of global states called global sequence
Note that g k [i] is well defined as the argument of max is a non-empty totally ordered (under
OE) finite set. It may evaluate to ? i which would mean that the process P i has not begun
its execution. Similarly, if it evaluates to ? i , then process P i has already terminated its
execution. The kth prefix of g, i.e. g 0 is denoted by g k .
We define findex(g; i.e., the first index in g which has u in its
global state. We define the set of global sequences consistent with a run r as linear(r), i.e.
The following theorem gives an alternative characterization of the set linear(r). Given
any g 2 linear(r) if the observer restricts his attention to a single process P i , then he would
observe r[i] or a stutter of r[i]. A stutter of r[i] is a finite sequence where each state in r[i]
may be repeated a finite number of times.
Lemma 1 For any run r, g 2 linear(r) if and only if the following constraints hold:
restricted to P (or a stutter of r[i])
Proof:
linear(r). This implies that 9C : C). Since C(s) is greater than 0 for
all s 6= ? i , we get that g 0 by definition of
C). Finally, g C[? i
holds. To see (S2), let s ! t. From (CC), we
get that C(s) ! C(t). This implies that findex(g; s) ! findex(g; t).
We define C as follows:
C satisfies (CC) due to (S2).
In our earlier paper[GarWal94], we have directly defined the notion of global sequences.
In this paper, we have chosen the condition (CC) based on global clocks as it is intuitively
easier to justify.
From the above two properties of global sequences, we can also deduce (S3):
says that for any set X of concurrent states there exists a global sequence g which
goes through a global state g k such that all local states in X occur in g k , and none occur in
D. Logic for Global Predicates
We now describe our logic for specification of global predicates. There are three syntactic
categories in our logic - bool, lin and form. The syntax of our logic is as follows:
form ::= A: lin j E: lin
lin ::= 3 lin j lin ,! lin
bool ::= a predicate over a global state
A bool is a boolean expression defined on a single global state of the system. Its value can be
determined if the global state is known. For example, if the global state has
then the bool (x  y) is true. Here x and y could be part of different processes. A lin is a
temporal formula defined over a global sequence. A bool is true in a global sequence if it is
true in the last state of g. 3 lin means that there exists a prefix of the global sequence such
that lin is true for the prefix. We also use 2 and  as duals of 3 and ". We have introduced
a binary operator (,!) to capture sequencing directly. p ,! q means that there exist prefixes
i and g j of the global sequence such that p is true of prefix g i , q is true of prefix g j , and
A form is defined for a run and it is simply a lin qualified A, and E quantify over the
set of global sequences that a run may exhibit, given the traces for each process. A:p means
that predicate p holds for all global sequences and E:p means that predicate p holds for some
global sequence. We call formulas starting with A: as strong formulas and formulas starting
with E: as weak formulas. The intuition behind the term strong is that a strong predicate
is true no matter how fast or slow the individual processes in the system execute so long
as the execution is consistent with the run. That is, it holds for all execution speeds which
generate the same trace for an individual process. A weak predicate is true if and only if
there exists at least one global sequence in which it is true. In other words, the predicate
can be made true by choosing appropriate execution speeds of various processors.
Semantics defined in this paper is slightly different from that in [GarWal94]. In [GarWal94]
bool is defined to be true on a global sequence if it is true in the first global state in the
sequence. In this paper, bool is required to be true in the last global state. The current
version is more useful and easier to understand. Intuitively, the logic in [GarWal94] is based
on future while the logic in this paper is based on past. Since the past is known at any point
of execution, it is easier to evaluate the formula in the current state.
Following are some examples of the strong formulas detectable by our algorithms.
1. Suppose we have developed an algorithm which works in phases. Assume that the
system has three nodes and that there are three phases in the algorithm. Let predicate
phase i;j denote that the process P i is in phase j. The following formula ensures that the
process P 2 is in phase 3, only after all the processes have been through phase 2.
phase 1;2 ,! phase 2;3 phase 2;2 ,! phase 2;3 phase 3;2 ,! phase 2;3 )
2. Suppose we were testing a commit protocol. Let Ready i denote the local predicate
that the process P i is ready to commit. Then, the following formula would check that there
was a certain point in the execution when all processes were ready to commit.
3. Suppose we wanted to test a distributed minimum spanning tree algorithm. Let
local predicate that the process P i knows its parent. Then, the following
formula would indicate that the system has reached a state in which all nodes in the network
know their parents.
3 Linked Predicates
This class of predicates is useful in detecting a sequence of events in a distributed program.
We use LP i to denote a local predicate in some process, and LP i (s) to denote that the
predicate LP i is true in the state s. We assume that the local predicate LP i is constructed
from only the local variables of that process. This means that the truthness of LP i can
change only through an internal event. In other words, external events cannot make any
local predicate change from true to false or vice-versa. Thus, a predicate such as "a message
has been sent from P to Q" is not considered a valid LP . Although this appears to be a
limitation, the above predicate can be easily modeled in our framework by assuming that an
internal event records the send of the message in some boolean variable such as msg sent.
The condition msg sent is a valid local predicate. The above assumption is equivalent to
the following:
1.
2. different from s and s:next.
(A1) says that if s and s:next differ in their evaluation of LP , then their causal relationships
with other states is identical.
We also use the following assumption.
's evaluate to false in the artificial states ? i and ? i for all i. This assumption
is also not a restriction. It just captures the intent of defining ? i and ? i states.
A predicate of the form A:LP i ,! LP j means that for all global sequences, there exists
an instance where LP i is true before LP j . A:(LP i ,! means that for all global
sequences there exists an instance where LP i is true before LP j which is true before LP k .
We treat ,! as a left associative operator and leave out the parentheses. We call a formula
of the form A: LP 1 ,! LP 2 ,! \Delta \Delta \Delta ,! LPm a strong linked predicate. The following theorem
is used in designing the algorithm for the detection of such predicates. Note that one side
of the proof (() is obvious. The converse, which is more difficult, has not been addressed
in the literature. This is one of the main results of this section.
Theorem 2 Let LP 1 and LP 2 be local predicates on processes i and j respectively. Then,
for any run r, there exist states s i in r[i] and s j in r[j], such that s
Proof: from (S1) we conclude that any global sequence
2 linear(r) has states g k and g l such that g k From (S2), we know
that findex(g; s
We show that if such states do not exist, then the formula A : LP 1 ,! LP 2 is
false (that is :LHS ) :RHS). If LP 1 (or LP 2 ) is not true for any state in r[i] ([r[j],
respectively), then the formula is trivially false. Consider the first state in r[i] in which LP 1
is true. We call this state s i . Similarly, s j is defined using the last state in r[j] in which
LP 2 is true. The negation of left hand side implies that s i 6! s j . Consider the state s j :next.
This state exists by (A2); it may be ? j . Let t be defined as
fsks j :nextg
Note that t could possibly be ? i . See Fig. 2.
global state

Figure

2: Linked Predicates
We now do case analysis.
Case 1: s
This means that s i is not concurrent with s j :next by the definition of t. Since s i 6! s j , we
get that s i 6! s j :next from (A1). This implies that s j :next ! s i which in turn implies that
t, a contradiction.
Case 2: t  s i
Since t is concurrent with s j :next, by Lemma (S3), there exists a global sequence g in which
t and s j :next occur in the same global state for the first time. The predicate LP 1 is not true
for all preceding global states and LP 2 is false for all following global states. Thus, there are
no two global states x, y such that LP 1 (x), LP 2 (y) and x occurs before y in g.
The above result can be generalized to a sequence of more than two local predicates
[GarWal94b].
The intuition behind the algorithm to detect the strong linked predicate (in Fig.
as follows. A:LP 1 ,! LP 2 is true only if the state in which LP 1 has occurred happened
before (!) the state in which LP 2 occurs. If both predicates are in the same process, then
occurrence of LP 1 would be known when LP 2 occurs. If LP 2 is in the different process then
by the definition of ! we know that there must be a message path to the second process.
We use the same message path to inform the second process about occurrence of LP 1 .
var
detectflag : boolean always (true iff curpred = m+ 1);
pred list: list of findex:1.m; pred:local predicate g
predicates local to this process;*/
curpred: integer initially
begin /* update what predicate is the next one this process is to detect*/
curpred++;
pred list := tail (pred list);
curpred:=max(curpred, hiscurpred);
To send /* we include curpred in message */

Figure

3: Algorithm for strong linked predicates
The implementation of the algorithm is as follows. The variable pred list in each process
keeps the list of logical predicates local to that process in the increasing order of indices in
which they appear in strong linked predicate. The variable curpred keeps the index of the
next local predicate in the strong linked predicate which needs to be detected (as currently
known by the process). If curpred becomes any process, then the strong linked
predicate is detected.
We now show the correctness of the above algorithm. Let link(s;
1. The predicate
link(s; 1) is defined to be true for all s. We also use s:x to refer to the value of the variable
x in the state s.
The following lemma describes an assertion on the variable curpred.
Lemma 3 For all local states s:
Proof: We show that the above assertion is true for the initial state and is maintained by
the program. Since curpred is initially 1, the assertion is trivially true for the initial state of
any process. For the induction case, let s OE im t. We assume that the assertion holds for s,
and show it to be true for t. we consider two cases:
Case 1: The event executed at s is not a receive
Since assertion holds for s, link(s; s:curpred) holds. Further, if LP s:curpred (s) is true then
link(t; s:curpred holds as s OE im t. It is also easy to see that s:curpred is the maximum
j such that link(t; holds. By incrementing s:curpred the assertion is maintained for t.
Case 2: A message is received at s which was sent from the state u
This part of the proof follows from the observation that link(s; implies that
link(t; j). If the assertion holds for s and u, then it is maintained by taking max of s:curpred
and u:curpred.
Theorem 4 At the termination of the algorithm, there exists a process for which detectflag
true if and only if the A: LP 1 ,! LP 2 ,! \Delta \Delta \Delta ,! LPm is true.
Proof: We first show that if the strong linked predicate is true, then it is detected by the
algorithm. Let the strong linked predicate be true. This means that at the termination there
exists a state s such that link(s; m + 1) is true. From Lemma 3, s:curpred
follows that the process which has state s will have its detectflag set.
Conversely, assume that s:detectf lag is true, i.e., s:curpred = m+ 1. Again from Lemma
3, this means that link(s; m+1) holds. From Theorem 2, this can happen only if A : LP 1 ,!
The above algorithm requires no extra messages but does require each message to contain
the value of curpred. Hence, each message grows in size by O(log m) bits where m is the
number of local predicates in the linked predicate.
The above algorithm can also be used to detect A
each DP i is a disjunction of local predicates. The only difference in detection of such a
predicate from the strong linked predicate is that an index may occur in pred list of more
than one process.
Miller and Choi [Mill88] have also proposed a similar algorithm for linked predicates.
In their algorithm, a process p sends out a predicate marker along each channel directed
away from p on detecting the local predicate. Thus, the algorithm assumes that underlying
communication channels are FIFO. Note that this assumption is also exploited in stopping
the program in a consistent state using an algorithm similar to that of Chandy and Lamport
[ChaLam85].
4 Strong Conjunctive Predicates
Conjunctive predicates form the most interesting class of predicates in our logic. A strong
conjunctive predicate is true if and only if the system will always reach a global state such
that all of the given local predicates are true in that state. Formally, a strong conjunctive
predicate is of the are local
predicates. Practically speaking, strong conjunctive predicates are most useful for good or
desirable predicates (i.e. predicates which the programmer would like to be true at some
point in the program). For example, in the case of a distributed two-phase commit protocol,
if the master decides to commit a transaction, then it must be true that the program was in
a global state where all the slaves were "ready" to commit. If the program is executed and
commits, but a global state where all slave processes are "ready" does not occur, then the
program has an error in it.
In this section, we present the conditions that are necessary and sufficient for a strong
conjunctive predicate to hold. This is one of the main results of this paper. These conditions
use the notion of intervals. An interval, I, is defined as a sequence of consecutive states of a
trace having a beginning state (designated as I:lo) and an ending state (designated as I:hi).
It is convenient to assume that I:lo and I:hi are distinct such that I:lo OE I:hi. This is not a
restriction. To model an interval with a single state it is sufficient to stutter that state once.
A set of intervals, I each belonging to a different process trace is said to overlap,
represented by, overlap(I only if the following holds:
Intuitively, the notion of overlapping intervals means that all the interval lo's are ordered
before all the interval hi's.
We assume that m  n and LP are local predicates in different processes,
(because LP 1 "LP 2 is just another local predicate if LP 1 and LP 2 belong to the
same process). We use LP (I) to denote that the local predicate LP is true for the entire
interval I.
The following Lemma shows that existence of overlapping intervals is sufficient to ensure
that all global sequences go through a global state in which (LP
Proof: Using the definition for overlapping intervals we know that:
This means that all lo 0 s must appear before all hi 0 s in any global sequence. Therefore, every
possible global sequence has a state greater than or equal to all lo 0 s and less than or equal
to all hi 0 s. In this state, the boolean expression LP true. Hence, the strong
conjunctive predicate A:
We now show that these conditions are also necessary. Our obligation is to show that if
these conditions are violated, then there exists a global sequence in which the strong conjunctive
predicate is false. Our proof of the existence of such a global sequence is constructive.
The global sequence we construct will have the property that it does not go through any
global state in which all LP i are true. We call such a global sequence pure. Formally,
Definition 6 A global sequence
We will construct a pure global sequence by concatenating together multiple pure global
subsequences. Let g be a global sequence of the run from a consistent global state x to a
consistent global state y (i.e. x is the first global state in g and y is the last global state in
g) and h be a global sequence from the global state y to a global state z. Then, it is easy to
see that g concatenated with h is also a global sequence from x to z. In constructing a pure
global sequence we use intermediate states which satisfy certain properties.
Let x be any global state. We denote by first(x) the m-tuple of intervals
where I k (x) is the first interval in r[k] which ends after the state x[k] in which LP k is true.
first(x) may not exist if for some process P k , LP k never becomes true after x[k]. A global
state is called consistent if We will use only consistent global states in our
description. The intermediate (consistent) global states that we use to construct our pure
global sequence satisfy an admissibility property.
Definition 7 x is an admissible intermediate global state if and only if either first(x) does
not exist or there exist k; l such that I k (x):lo 6! I l (x):hi " :LP k (x[k]).
In other words, there exists two intervals I k and I l such that they do not overlap (I k (x):lo 6!
I l (x):hi) and LP k is not true in the state x[k].
Now, we are ready to show that:
Lemma 8
Proof:
global state x a b
c
{ (a,c,d), (b,c,d), (a,c,e), (b,c,e) }

Figure

4: I(x) and first(x)
Let I(x) for any global state x be the set of all m-tuple of intervals in which LP i is true
for the i th trace (see Fig. 4) after the local state x[i]. We show that if none of these m-tuple
of intervals satisfy overlapping condition, then there exists a global sequence in which the
distributed program is never in any m-tuple in X.
Our aim is to construct a pure global sequence g from start
x be any global state such that we have built a pure global sequence
from start to x, and the remaining task is to build a pure global sequence from x to stop.
Initially, we choose start. We will show a pure global sequence from x to y such that
jI(x)j. Thus, by continuing in this manner we will reach a global state z in which
that point all global sequences will be pure.
The start state is admissible, because by assumption either first(start) does not exist or
there exist k; l such that I k (start):lo 6! I l (start):hi. Moreover, LP k is false in ? k by (A2).
Now suppose that we are given an admissible global state x such that jI(x)j ? 0. For
be the first interval in r[j] in which LP j is true that ends after the
state x[j]. As x is admissible and first(x) exists (jI(x)j ? 0), there exist k; l such that
I k (x):lo 6! I l (x):hi and :LP k (x[k]). We define s to be the local state I l (x):hi:next. The
state s exists because of (A2) (it may be ? l ). We construct a global sequence from x
to another admissible global state y, where y is defined as the minimum consistent global
state such that Such a global state exists because the set of all consistent cuts
(ideals) is a lattice [Matt89] and that ideals grow by adding one element at a time [DJR93].
We first show that LP k is never true between x[k] and y[k]. It is sufficient to show that
We know that I k (x):lo 6! I l (x):hi. Applying (A1) twice, it follows that
I k (x):lo:prev 6! I l (x):hi:next. Thus, there exists a consistent global state z containing s
such that z[k]  I k (x):lo:prev. As y is the minimum consistent global state with
we get that y[k]  I k (x):lo:prev. This implies that LP k is never true between x[k] and y[k].
Thus, all global sequences from x to y are pure. See Figure 5.
x
Ik
Il
y
Ik'
Il'
s

Figure

5: Illustration of the proof of strong conjunctive predicates
We still need to show that y is admissible. If first(y) does not exist, we are done.
Otherwise, we know that there exist k 0 ; l 0 such that I k 0
(y):lo 6! I l 0
(y):hi (see Fig. 5). If
then y is an admissible state and we are done. Otherwise, y[k 0 ] is inside the
interval I k 0
(y). If I k 0
(y):lo:prev 6! s, then we can find a consistent global state z such that
(y):lo:prev such that y is the minimum state with
I k 0
(y):lo  y[k 0 ], z cannot exist. Thus, I k 0
From (A1) this is equivalent to
I k 0
We now show that y is admissible because I l (y):lo 6! I l 0
(y[l]). The second
conjunct is clearly true by the definition of y. We show the first conjunct. From I k 0
I l (x):hi, and I l (x):hi OE I l (y):lo it follows that I k 0
I l (y):lo. Therefore, I l (y):lo !
I l 0
(y):hi is inconsistent with I k 0
(y):lo 6! I l 0
(y):hi. Thus, the first conjunct I l (y):lo 6! T l 0
(y):hi
also holds.
We see from the necessary and sufficient conditions for a strong conjunctive predicate to
hold that the intervals delimited by lo 0 s (local predicate transitioning from false to true) and
hi's (transitions from true to false) must overlap.
At this point, we discuss the role of (A2). Consider a scenario in which two processes
are such that LP 1 and LP 2 are true throughout the execution of P 1 and P 2
respectively. If P 1 and P 2 never communicate with each other, then there does not exist
overlapping intervals for LP 1 and LP 2 . However, it may seem to the reader that for any
global sequence there is a global state in which both LP 1 and LP 2 are true. The global
sequence for which there does not exist any global state satisfying the strong conjunctive
predicate is obtained by running one process to the completion before the other starts.
Clearly, unless execution of both processes are synchronized in some manner, the above
sequence is a proper global sequence. By (A2) LP 1 and LP 2 are false at the initial state
(before the process has begun execution) and at final state (after the process has finished its
execution).
4.1 Algorithms for Detecting A Strong Conjunctive Predicate
We now describe algorithms to check whether intervals in which local predicates hold overlap.
These algorithms are executed by two kinds of processes - nonchecker processes and checker
processes. They are based on a slight modification of timestamp vectors as proposed by
Fidge[Fidge88] and Mattern [Matt89]. Each process detects its local predicate and records
the timestamp of the interval associated with the predicate. These intervals are sent to a
checker process which uses them to decide if the strong conjunctive predicate became true.
Each non-checker process its own local lcmvector of timestamps. For process
is the message id of the last message from P i (to anybody) which
has a causal relationship to P j . lcmvector[j] for process P j is the next message id that P j will
use. Each time the local predicate of a process changes from false to true, the current value
of lcmvector is remembered as an interval lo. At the next true-to-false transition (denoted
by # in the Fig. 6), the process sends the stored lcmvector (interval lo) and the current
lcmvector (interval hi) to the checker process in a debug message. We next observe that a
process is not required to send its interval every time the local predicate is detected. The
interval need not be sent if there has been no message activity since the last time the interval
was sent. This is because the lcmvector can change its value only when a message is sent
or received. We now show that it is sufficient to send a lcmvector once after any message is
received irrespective of the number of messages sent.
Let predicate firstlmr(I) be true iff the local predicate is true in I for the first time
since the last message was received (or the beginning of the trace). We say scp(I
is true if I 1 are the intervals in different processes making the strong conjunctive
predicate true (as in Theorem 5).
Theorem 9 9I
Proof: By symmetry it is sufficient to prove the existence of J 1 such that scp(J 1
be the first interval in the trace of P 1 such that LP (J 1 ) is true. Since
our proof obligation is to show that scp(J 1 It is sufficient
to show that overlap(J 1 m. For any I k , I 1 :lo ! I k :hi and J 1
therefore, Moreover, as there is no
message received after J 1 :hi and before I 1 :hi, the last causal message that made I k :lo ! I 1 :hi
true must have arrived before J 1 :hi. Therefore, it is also true that I k :lo ! J 1 :hi. Hence, we
conclude that overlap(J 1 ; I k ).
Process P id ::
var
lcmvector: array [1.n] of (0.MAXMID);
init 8i:i 6=id:
last causal msg rcvd from process 1 to n, respec. */
Current Interval: record lo, hi : (0.MAXMID);end;
firstflag: boolean init true;
local pred: Boolean Expression; /*the local pred. to be tested by this process*/
2 For sending do
send (prog, midgen,
Upon receive (prog, mid, msg
firstflag := true;
Upon (local pred ") " firstflag do
Current Interval.lo := lcmvector;
Upon (local pred #)" firstflag do
Current Interval.hi := lcmvector;
send (dbg, Current Interval) to CHECKERPROC;
firstflag := false;

Figure

Algorithm for strong conjunctive processes - nonchecker process P id
The dominant space complexity of the above algorithm is due to the array "lcmvector"
which is O(n). The main time complexity involves detecting the local predicates which is
the same as for a sequential debugger. In the worst case, one debug message is generated for
each program message received, so the worst case message complexity is O(m r
the number of program messages received.
We now give the algorithm for the checker process which detects the strong conjunctive
predicate using the debug messages sent by other processes. The checker process has a separate
queue for each process involved in the strong conjunctive predicate. Incoming debug
messages from processes are enqueued in the appropriate queue. We ensure that the checker
process gets its message from any process in a FIFO order. The required computation to
var
queue of record lo, hi: timevector;end;
changed, newchanged: set of f1,2,.,mg
Upon recv(elem) from P k do
changed
while (changed 6= OE) begin
newchanged := fg;
for i in changed, and j in [1,2,.,m] do begin
newchanged:=newchanged [ fig;
newchanged:=newchanged [ fjg;
end; /* for */
changed := newchanged;
for i in changed do deletehead(q i );
end;/* while */

Figure

7: Algorithm for strong conjunctive checker process
check if the lcmvector u is less than the vector v in a different process is
I and J be intervals in processes P i and P j with vector pairs x and y,
respectively. Then, overlap(I; J) iff (x:lo
Proof: The proof follows from the fact that if s and t are states with time vectors u and v,
Thus, the task of the checker process is reduced to checking ordering between lcmvectors
to determine if the intervals overlap. Because of the above Lemma, we use terms intervals
and vector-pairs interchangeably. The following Lemma shows how the checker process can
avoid checking all possible combinations of intervals.
Lemma 11 Let x and y be two vector pairs at the head of their respective queues. If they
do not overlap, then at least one of them can be eliminated from further consideration in
checking to see if the strong conjunctive predicate is satisfied.
Proof: In order for the strong conjunctive predicate to be true, there must exist a set of
intervals, one from each queue, such that each overlaps with all the others in the set. Let two
intervals x and y be at the head of their queues such that they do not overlap. This means
that either x:lo 6! y:hi or y:lo 6! x:hi. Assume the former without any loss of generality. We
show that y can be eliminated in this case. If not, let x 0 be another interval in the queue
of x which overlaps with y. This implies that x
that x:lo ! y:hi, a contradiction.
The checker process receives debug messages containing timestamp pairs from the other
processes and executes the algorithm in Fig. 7. Each element of the queue is an interval,
and the comparisons are done between hi 0 s and lo 0 s of these intervals. The checker process
reduces the number of comparisons by deleting any vector-pair at the head of any queue
whose hi lcmvector is not greater than lo lcmvector of vector-pairs of head of all other
queues. The checker process has detected the strong conjunctive predicate to be true if it
finds a set of intervals at the head of queues such that they are pairwise overlapping.
This algorithm requires at most O(m 2 p) comparisons where m is the number of queues
each of length at most p.
5 Decentralization of the Algorithm
We now show techniques for decentralizing the above algorithm. If a set of intervals S is
such that all pairs of intervals overlap, then the following holds:
We denote this by predicate overlap(S). Our aim is to show that the above condition can
be checked in a decentralized manner. For this, we need the concept of greatest lower bound
of a set of intervals. Let X be set of all intervals, where each interval x is defined as a pair
of vectors x:lo and x:hi such that x:lo  x:hi. We now define an order v between elements
in this set as follows:
It can be easily checked that (X ; v) is a partial order. In this partial order, x u
Further, if x are such that
The following theorem shows that the process of finding overlap(X) can be decomposed
into smaller sets.
Theorem 12 Let X;Y , and Z be sets of intervals, such that
are clearly true because Y; Z ' X. We need to show
that
Let y  Zg. Since overlap(Y ) and overlap(Z), y   and z
belong to X . To prove overlap(y   ; z   ), we need to show that (y   :lo ! z
We show just the first conjunct.
From overlap(X), we get that
In particular,
Then, by definition of y   and z   , we conclude that
y   :lo ! z   :hi
We show that (P 1) holds for X, i.e.
If both y and z belong either to Y and Z, then the above is true from overlap(Y ) and
overlap(Z). Let us assume without loss of generality that y 2 Y and z 2 Z. We need to
show that y:lo ! z:hi. This is true because y:lo  y   :lo ! z   :hi  z:hi. The first and the
last inequality follow from the definition of y   and z   ; the middle inequality follows from
overlap(y   ; z   ).
Using the above theorem and the notions of a hierarchy, the algorithm for checking
the strong conjunctive predicate can be decentralized as follows. We may divide the set
of processes into two groups. The group checker process checks for the strong conjunctive
predicate within its group. On finding one, it sends the greatest lower bound of all intervals
to a higher process in the hierarchy. This process checks the last conjunct of the above
theorem. Clearly, the above argument can be generalized to a hierarchy of any depth.
6 Applications
The main application of our results are in debugging and testing of distributed programs. We
have incorporated our algorithms in a distributed debugger [Hoagla92]. The online debugger
is able to detect global states or sequences of global states in a distributed computation.
The architecture of this distributed debugger is shown in Figure 8. With each application
process, we attach two processes - a gdb process and a monitor process. gdb is a sequential
debugger that we use for detecting local predicates. monitor processes are responsible for
attaching vector time information with all messages. They also report to the centralized
coordinator process whenever an interval is detected. Monitor processes also detect strong
linked predicates using the algorithm outlined earlier. There is one coordinator process in
the system. It receives all the information from monitor processes and checks for strong
and weak conjunctive predicates. The coordinator also provides a single user-interface to
the programmer. Our distributed debugger runs on a cluster of SUN workstations running
SUNOS.
application
process gdb
application
process gdb
coordinator
* user-interface
* checker algorithm for SCP
monitor monitor
* vector
clocks
* SLP
algorithm

Figure

8: Architecture of Our Distributed Debugger
We have also used our algorithms to implement a trace analyzer for distributed programs
[Chin91]. Our analyzer monitors a distributed program and gathers enough information to
form a distributed run. The user can then ask whether any global predicate became true.
Conclusions
We have discussed detection of global predicates in a distributed program. Earlier algorithms
for detection of global predicates proposed by Chandy and Lamport work only for stable
predicates. Our algorithms detect even unstable predicates with reasonable time, space and
message complexity.
In this paper, we have emphasized conjunctive predicates and not disjunctive predicates.
The reason is that disjunctive predicates are quite simple to detect. Disjunctive predicates
are of the form A:LP 1  LP or of the form E:LP 1  LP It turns
out that for the simple case considered here, both expressions are equivalent. To detect a
disjunctive predicate A:LP 1 LP it is sufficient for process P i to monitor LP i .
If any of the process finds its local predicate true, the disjunctive predicate is true.
We have also not discussed predicates of the form A : 2bool. These predicates are duals
which have been discussed in [GarWal94].
Algorithms given in this paper detect predicates of the form A:3bool, where bool is a
conjunction of local predicates. It would be of great interest if these algorithms can be
generalized to detect predicates when bool is any boolean expression of local predicates.

Acknowledgements

We would like to thank Bryan Chin, Mohamed Gouda, Greg Hoagland, Jay Misra, Michel
Raynal, and Alex Tomlinson for their comments on earlier versions of this work. We would
also like to thank Bryan Chin for implementing offline versions of our algorithms and Greg
Hoagland for incorporating our algorithms in a distributed debugger. We also thank anonymous
referees for their meticulous review of an earlier version of the paper.



--R

"Consistent global states of distributed systems: fundamental concepts and mechanisms"
"Distributed Debugging Tools for Heterogeneous Distributed Sys- tems"
"Repeated Snapshots in Distributed Systems with synchronous communication and their implementation in CSP"
"Distributed Snapshots: Determining Global States of Distributed Systems"
"An Offline Debugger for Distributed Programs"
"Consistent Detection of Global Predicates"
"Reachability Analysis on Distributed Executions"
"Partial Orders for Parallel Debugging"
"Detection of Unstable Predicate in Distributed Programs,"
"Using Induction to Prove Properties of Distributed Programs"
"Detection of Weak Unstable Predicates in Distributed Programs,"
"Detection of Strong Unstable Predicates in Distributed Programs,"
"Global events and global breakpoints in distributed systems"
"A Debugger for Distributed Programs"
"Detecting Atomic Sequences of Predicates in Distributed Computations,"
"Time, Clocks, and the Ordering of Events in a Distributed System"
"Virtual time and global states of distributed systems"
"Debugging Concurrent Programs"
"Breakpoints and Halting in Distributed Programs"
"Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail"
"Efficient Distributed Snapshots"
"Simultaneous Regions: A Framework for Consistent Monitoring of Distributed Systems,"
"Detecting Relational Global Predicates in Distributed Systems,"
"Unstable Predicate Detection in Distributed Programs,"
--TR

--CTR
Sridhar Alagar , Subbarayan Venkatesan, Techniques to Tackle State Explosion in Global Predicate Detection, IEEE Transactions on Software Engineering, v.27 n.8, p.704-714, August 2001
Hsien-Kuang Chiou , Willard Korfhage, ENF event predicate detection in distributed systems, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.91-100, August 14-17, 1994, Los Angeles, California, United States
Punit Chandra , Ajay D. Kshemkalyani, Distributed algorithm to detect strong conjunctive predicates, Information Processing Letters, v.87 n.5, p.243-249, 15 September
Loon-Been Chen , I-Chen Wu, An Efficient Distributed Online Algorithm to Detect Strong Conjunctive Predicates, IEEE Transactions on Software Engineering, v.28 n.11, p.1077-1084, November 2002
Ajay D. Kshemkalyani, A Fine-Grained Modality Classification for Global Predicates, IEEE Transactions on Parallel and Distributed Systems, v.14 n.8, p.807-816, August
Alexander I. Tomlinson , Vijay K. Garg, Detecting relational global predicates in distributed systems, ACM SIGPLAN Notices, v.28 n.12, p.21-31, Dec. 1993
Jean-Michel Hlary , Achour Mostefaoui , Michel Raynal, Communication-Induced Determination  of Consistent Snapshots, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.865-877, September 1999
Guy Dumais , Hon F. Li, Distributed Predicate Detection in Series-Parallel Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.4, p.373-387, April 2002
Craig M. Chase , Vijay K. Garg, Detection of global predicates: techniques and their limitations, Distributed Computing, v.11 n.4, p.191-201, October 1998
Vijay K. Garg, Methods for Observing Global Properties in Distributed Systems, IEEE Parallel & Distributed Technology: Systems & Technology, v.5 n.4, p.69-77, October 1997
J.-M. Hlary , A. Mostefaoui , R. H. B. Netzer , M. Raynal, Communication-based prevention of useless checkpoints in distributed computations, Distributed Computing, v.13 n.1, p.29-43, January 2000
Ashis Tarafdar , Vijay K. Garg, Predicate control: synchronization in distributed computations with look-ahead, Journal of Parallel and Distributed Computing, v.64 n.2, p.219-237, February 2004
Scott D. Stoller, Detecting global predicates in distributed systems with clocks, Distributed Computing, v.13 n.2, p.85-98, April 2000
Punit Chandra , Ajay D. Kshemkalyani, Causality-Based Predicate Detection across Space and Time, IEEE Transactions on Computers, v.54 n.11, p.1438-1453, November 2005
Felix C. Grtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999
predicate detection;unstable predicates;distributed debugging;distributed algorithms