Detecting global predicates in distributed systems with clocks.
This paper proposes a framework for detecting global state predicates in systems of processes with approximately-synchronized real-time clocks. Timestamps from these clocks are used to define two orderings on events: "definitely occurred before" and "possibly occurred before". These orderings lead naturally to definitions of 3 distinct detection modalities, i.e., 3 meanings of "predicate  held during a computation", namely: Poss <sup><i>db</i></sup>  (" possibly held"), definitely held"), and Inst  (" definitely held in a specific global state"). This paper defines these modalities and gives efficient algorithms for detecting them. The algorithms are based on algorithms of Garg and Waldecker, Alagar and Venkatesan, Cooper and Marzullo, and Fromentin and Raynal. Complexity analysis shows that under reasonable assumptions, these real-time-clock-based detection algorithms are less expensive than detection algorithms based on Lamport's happened-before ordering. Sample applications are given to illustrate the benefits of this approach.
Introduction
A history of a distributed system can be modeled as a sequence of events. Since execution
of a particular sequence of events leaves the system in a well-defined global state, a history
uniquely determines the sequence of global states through which the system has passed. Un-
fortunately, in a distributed system without perfect clock synchronization, it is, in general,
A preliminary description of this work appeared in [30].
y Scott D. Stoller (stoller@cs.indiana.edu, www.cs.indiana.edu/~stoller/) is with the Department of Computer
Science, Indiana University, Bloomington, IN.
impossible for a process to determine the order in which events on different processors actually
occurred. Therefore, no process can determine the sequence of global states through
which the system passed. This leads to an obvious difficulty for detecting whether a global
state predicate (hereafter simply called a "predicate") held.
Cooper and Marzullo proposed a solution for asynchronous distributed systems [6]. Their
solution involves two modalities, which we denote by Poss hb
initely"). These modalities are based on logical time [18] as embodied in the happened-
before relation hb
!, a partial ordering 1 of events that reflects potential causal dependencies.
Happened-before is not a total order, so it does not uniquely determine the history, but
it does restrict the possibilities. Given a predicate \Phi, a computation satisfies Poss hb
there is some interleaving of events that is consistent with happened-before and in which
the system passes through a global state satisfying \Phi. A computation satisfies
for every interleaving of events that is consistent with happened-before, the system passes
through a global state satisfying \Phi.
Cooper and Marzullo's definitions of these modalities established an important conceptual
framework for predicate detection in asynchronous systems, which has been the basis
for considerable research [8, 13, 4, 17, 32, 14, 5, 12]. In practice, though, Poss hb
other modalities based on happened-before have significant drawbacks in many cases. First,
in many systems, it is difficult to determine the happened-before relation. Happened-before
can be determined if each process maintains a vector clock. This requires that a vector
timestamp with O(N) components be attached to every message, where N is the number
of processes in the system, and imposes computational overhead of O(N) operations per
message received (to update the vector clock). Generating code that inserts and removes
the vector timestamps without changing the existing types in the programs (which would
open a can of worms) or copying entire messages (which is inefficient) can be difficult. If
the programs use a stream-oriented communication protocol that does not provide message
boundaries, such as TCP, the difficulty is significantly compounded, since a receiver might
receive a fragment of a "message" or several "messages" in a single receive event. Further-
more, piggybacking vector timestamps requires changing all communication statements in
the application, even if the predicate of interest involves the state of only one module. If
source code is not available for part of the system, this might be impossible. Happened-
before can be determined without vector clocks, if all processes inform the monitor of all
send events and receive events and provide the monitor with enough information to determine
the correspondence between send and receive events (i.e., for each receive event, the
monitor can determine which send event sent the received message). However, this method
1 In this paper, all partial orderings are irreflexive unless specified otherwise.
often has significant drawbacks, too. In general, determining the correspondence between
send and receive events requires piggybacking an identifier (e.g., a sequence number) on each
message; this involves the same difficulties as piggybacking a vector timestamp. 2 An additional
drawback of this method is that the monitor must be informed of all send events and
receive events. With vector timestamps (or if the happened-before relation is not needed),
it suffices to inform the monitor only of events that might change the truth value of the
predicate of interest; 3 this can significantly reduce the amount of information sent to the
monitor.
A second drawback of detecting Poss hb
\Phi is the computational cost: the
worst-case time complexity is \Omega\Gamma E N ), where E is the maximum number of events executed
by any process. The worst case occurs when there is little or no communication and hence
few causal dependencies, so that many interleavings must be explored. For example, this
exponential cost was seen in two sample applications considered in [31], namely, a coherence
protocol and a spanning-tree algorithm. A third drawback is that, in systems with hidden
channels [2] (i.e., means of communication other than messages), happened-before does not
accurately capture causal relationships, so Poss hb
\Phi do not accurately capture
the meanings of "possibly held" and "definitely held".
This paper proposes a framework for predicate detection in systems with approximately-
synchronized real-time clocks. Timestamps from these clocks can be used to define two
orderings on events: db
("definitely occurred before") and pb
("possibly occurred before").
By (roughly speaking) substituting each of these orderings for happened-before in the definitions
of Poss hb
and
, we obtain definitions of four new modalities. The two modalities
based on db
are closely analogous to Poss hb
and
, so we denote them by Poss db
and
. We obtain algorithms for detecting Poss db
and
by adapting algorithms of Garg
and Waldecker [13, 14], Alagar and Venkatesan [1], and Cooper and Marzullo [6]. Modalities
based on pb
are quite different, because pb
and db
!) is not a partial ordering. In
yields a degenerate case, in which the analogues of Poss hb
and
are equivalent.
We show that this single modality, which we denote by Inst, is closely related to Fromentin
and Raynal's concept of Properly hb
and we adapt for detecting Inst an algorithm
of theirs for detecting Properly
.
Our detection framework is applicable to a wide range of systems, since it does not
require that clocks be synchronized to within a fixed bound. However, the quality of clock
synchronization does affect the two event orderings just described and therefore the results
Even if the underlying communication protocol uses sequence numbers, operating-system protection
mechanisms may prevent the monitoring system from accessing them.
3 This optimization is not explicitly incorporated in our algorithms, but that is easily done.
of detection. For example, consider Inst \Phi. Informally, a computation satisfies Inst \Phi iff
the timestamps imply that there was an instant during the computation when predicate \Phi
held, i.e., iff there is some collection of local states that form a global state satisfying \Phi
and that, based on the timestamps, definitely overlapped in time. Suppose \Phi actually holds
in a global state g that persists for time ffi. Whether Inst \Phi holds depends on the quality
of synchronization. Roughly, if the maximum difference between clocks is known to be less
than ffi, then Inst \Phi holds; otherwise, there is in some cases no way to determine whether
the local states in g actually overlapped in time, so Inst \Phi might not hold.
The quality of clock synchronization affects also the cost of detection. For example,
consider Poss
db
\Phi. Informally, a computation satisfies Poss
db
\Phi iff there is some collection of
local states that form a global state satisfying \Phi and that, based on the timestamps, possibly
overlapped in time. The larger the error in clock synchronization, the more combinations of
local states possibly overlap. In general, \Phi must be evaluated in each such combination of
local states. Thus, the larger this error, the more expensive the detection. If this error is
bounded relative to the mean interval between relevant events (i.e., events that potentially
truthify or falsify \Phi), then the number of global states that must be checked is linear in E.
In the asynchronous case, the number of global states that must be checked is O(E N ).
The above condition on the error in clock synchronization holds in many systems. In most
local-area distributed systems, protocols like NTP can efficiently maintain synchronization
of clocks to within a few milliseconds [26]. Even in extremely wide-area distributed systems
like the Internet, clock synchronization can usually be maintained to within a few tens of
milliseconds [24, 26]. The detection framework and algorithms proposed here are designed
to provide a basis for monitoring and debugging applications in such systems. Some sample
applications are described in Section 7, including applications in which timers provide a
hidden channel, causing detection based on happened-before to be less appropriate.
Directions for future work include: implementing the detection algorithms described
above; developing efficient algorithms for detecting global properties that depend explicitly
on time; and investigating clock-based detection of sequences of global states, perhaps along
the lines of temporal modalities based on happened-before [16, 3, 11].
Related Work
Marzullo and Neiger [23] discuss global property detection in partially-synchronous systems
in which a fixed bound ffl on the error between clocks is known. In the notation of this paper,
they define modalities Poss hd
and
!, and give detection algorithms
for these two modalities. Combining happened-before and real-time ordering exploits more
information about the computation and hence is certainly desirable whenever it is feasible.
Modifying the algorithms in this paper to take happened-before into account is a straight-forward
exercise, and the resulting algorithms would be appropriate for monitoring some
systems. This paper presents algorithms that do not use happened-before for three reasons.
First and most important, as discussed in Section 1, it is often difficult in practice to modify
a system so that the monitor can determine the happened-before relation; consequently,
detection algorithms that depend on happened-before have limited applicability. 4 Second,
not using happened-before enables some optimizations (specifically, those involving priority
queues) that are impossible if causal ordering is also used. Third, incorporating happened-
before would have obscured the presentation and complexity analysis of the real-time-based
parts of the algorithms, which are the novel parts.
Contributions of this paper relative to [23] include: detection algorithms based purely
on real-time clocks; more efficient detection algorithms; and definition of and algorithm for
Inst. [23] does not consider any modality analogous to Inst. Also, [23] assumes a fixed
bound on the error in clock synchronization. Our framework allows that bound to vary over
time; this supports tighter bounds hence more accurate monitoring results.
An attractive feature of Properly hb
Inst is that the monitor can report a
single global state g satisfying \Phi that the system actually passed through. does not have
this feature. However, Properly hb
gives useful information only about systems that perform
global (i.e., system-wide) barrier synchronization. Such synchronization is expensive and
rarely used. In contrast, assuming reasonably good clock synchronization, Inst is informative
even in the absence of barrier synchronization. Since Inst, like Properly hb
! , can be detected
efficiently for arbitrary predicates, it appears to be a useful modality.
The "possibly occurred before" relation pb
is reminiscent of Lamport's ``can affect'' relation
for concurrent systems [20, 21]. Both relations may contain cycles because of overlap:
for pb
!, overlap of interval timestamps; for "can affect", overlap of non-atomic events. Our
framework assumes events are atomic; this is appropriate for systems with message-based
communication.
Ver'issimo [33] discusses the uncertainty in event orderings caused by the granularity 5 and
imperfect synchronization of digital real-time clocks, analyzes the conditions under which
this uncertainty is significant for an application, and describes a synchronization technique,
suitable for certain applications, that masks this uncertainty. However, [33] does not aim for
a general approach to detecting global properties in the presence of this uncertainty.
4 Our algorithms apply directly even to programs that use high-level communication libraries (e.g., a
distributed shared memory (DSM) library) for which source code is not available; detecting happened-before
in such cases would be difficult.
5 Our framework accommodates the granularity of digital clocks by using - instead of ! in TS1 and TS2.
3 Background
A computation of a single process is called a local computation and is represented as a finite
or infinite sequence of local states and events. Thus, a local computation has the form
where the e ff are events, and the s ff are local states. By convention, e 1 corresponds to
creation of the process. If the sequence is finite, it ends with an event that corresponds (by
convention) to the termination of the process.
A computation of a distributed system is a collection of local computations, one per pro-
cess. A computation is represented as a function from process names to local computations.
We use integers process names; thus, for a computation c, the local computation
of process i is c(i). Variables i and j always range over process names. We use Ev(c)
and St(c) to denote the sets of all events and all local states, respectively, in a computation
c. For convenience, we assume that all events and local states in a computation are distinct.
The following functions are implicitly parameterized by a computation; the computation
being considered should be evident from the context. For an event e, pr(e) denotes the
process on which e occurs. For a local state s, pr(s) denotes the process that passes through
s, and S(s) and T (s) denote the start event and terminal event, respectively, of s. For
example, for a computation containing local computation (1), S(s 2 ) is e 2 , and T (s 2 ) is e 3 .
A global state of a distributed system is a collection of local states, one per process,
represented as a function from process names to local states. The set of global states of a
computation c is denoted GS (c); thus, g is in GS (c) iff for each process i, g(i) is a local state
in c(i). We define a reflexive partial ordering - on global states by:
occurs before g 0 (i)): (2)
All of the orderings defined in this paper, including -, are implicitly parameterized by a
computation; the computation being considered should be evident from the context.
Each event e has an interval timestamp C(e), which is an interval with lower endpoint
We model events as being atomic and instantaneous;
the width of the interval timestamp depends only on the quality of clock synchronization
when the event occurs. We assume that the interval timestamps are non-decreasing and are
consistent with the order of events; more precisely, we assume:
TS1. For every event e, C 1
TS2. For every event e 1 with an immediately succeeding event e 2 on the same process,
TS3. For every event e 1 and every event e 2 , if e 1 occurred before e 2 , then C 1
There are various ways of satisfying these assumptions, depending on the underlying clock
synchronization mechanism. As a simple (yet realistic) example, if the clock synchronization
algorithm never decreases the value of a clock, and if all of the machines (more precisely, all
of the machines relevant to the predicate being detected) synchronize to a single time server,
then TS1-TS3 hold if timestamps are chosen such that the value of the time server's clock
was in the interval C(e) when event e occurred. Thus, a machine can take C 1
and C 2 is the value of its local clock when e occurred, and " is a bound
on the difference between its clock and the time server's clock when e occurred. In systems
in which time servers are organized in peer groups or in a client-server hierarchy, C(e) can
be determined from an appropriate combination of the bounds on the errors between the
relevant clocks. In either case, the information needed to construct interval timestamps can
be obtained from standard clock synchronization subsystems, such as NTP [25, 26] or the
Distributed Time Service in OSF DCE [27].
4 Generic Theory of Consistent Global States
Predicate detection in asynchronous systems is based on the theory of consistent global
states (CGSs) [2]. Informally, a global state is consistent if it could have occurred during
the computation. It is convenient to define "consistent" in terms of ideals. Recall that an
ideal of a partial order hS; OEi is a set I ' S such that (8x 2 I : 8y
of hEv(c); hb
!i are called consistent cuts [2]. Recall that for any partial order, the
set of its ideals ordered by inclusion (') forms a lattice [8]. Furthermore, the set of CGSs
ordered by - forms a lattice that is isomorphic to the lattice of consistent cuts [28, 2].
This isomorphism has an important consequence for detection algorithms: it implies that
a minimal increase with respect to - corresponds to advancing one process by one event
(because adjacent ideals of hEv(c); hb
!i differ by exactly one event) and hence that the lattice
of CGSs can be explored by repeatedly advancing one process by one event. This principle
underlies detection algorithms of Cooper and Marzullo [6], Garg and Waldecker [13, 14], and
Alagar and Venkatesan [1].
In this section, we show that the above theory is not specific to the happened-before
relation but rather applies to any partial ordering ,! on events, provided ,! is process-wise-
total, i.e., for any two events e 1 and e 2 on the same process, if e 1 occurred before e 2 , then
This generalized theory underlies the detection algorithms in Sections 5 and 6.
Definition of CGSs. Let c be a computation, and let ,! be a relation on Ev(c). We
define a relation / ,! on St(c), with the informal interpretation: s / ,! s 0 if s ends before s 0
starts. Formally,
Two local states are concurrent with respect to ,! if they are not related by / ,! . A global
state is consistent with respect to ,! if its constituent local states are pairwise concurrent:
consis ,! (g) \Delta
Thus, the set of CGSs of computation c with respect to ,! is
Note that CGS hb
! is the usual notion of CGSs.
Definitions of Poss and . The modalities Poss hb
and
for asynchronous systems
are defined in terms of the lattice hCGS hb
We generalize them as follows.
A computation c satisfies Poss ,! \Phi iff CGS ,! (c) contains a global state satisfying
\Phi.
,! is defined in terms of paths. A path through a partial order hS; -i is a finite or infinite
sequence 6 oe of distinct elements of S such that: (i) oe[1] is minimal with respect to -; (ii)
for all ff is an immediate successor 7 of oe[ff]; and (iii) if oe is finite,
then oe[joej] is maximal with respect to -. Informally, each path through hCGS ,! (c); -i
corresponds to an order in which the events in the computation could have occurred.
A computation c satisfies every path through hCGS ,! (c); -i contains
a global state satisfying \Phi.
CGSs and Ideals. When ,! is a process-wise-total partial ordering, there is a natural
correspondence between CGS ,! (c) and ideals of hEv(c); ,!i. One can think of an ideal I as
the set of events that have occurred. Executing a set I of events leaves each process i in the
local state immediately following the last event of process i in I. Thus, ideal I corresponds
6 We use 1-based indexing for sequences.
7 For a reflexive or irreflexive partial order hS; OEi and elements x 2 S and y 2 S, y is an immediate
successor of x iff x
to the global state g such that for all i, S(g(i)) is the maximal element of fe 2 I j ig.
This correspondence is an isomorphism.
Theorem 1. For every process-wise-total partial ordering ,! on Ev(c), the partial order
hCGS ,! (c); -i is a lattice and is isomorphic to the lattice of ideals of hEv(c); ,!i.
Proof. This is true for the same reasons as in the standard theory based on happened-before
[28, 2, 8]. The proof is straightforward.
The following corollary underlies the detection algorithms in Sections 5 and 6.
Corollary 2. For any process-wise-total partial ordering ,!, if global state g 0 is an immediate
successor of g in hCGS ,! (c); -i, then the ideal corresponding to g 0 contains exactly one
more event than the ideal corresponding to g.
Proof. This follows from Theorem 1 and the fact that for any partial order S, if one ideal
of S is an immediate successor of another ideal of S, then those two ideals differ by exactly
one element.
Detection Based on a Strong Event Ordering: Poss db
and
We instantiate the generic theory in Section 4 with the partial ordering db
("definitely
occurred before"), defined by:
db
This ordering cannot be defined solely in terms of the timestamps C(e 1 ) and C(e 2 ), because
TS1 and TS2 allow consecutive events on a process to have identical timestamps. Therefore,
we assume that a process records a local sequence number as well as an interval timestamp
for each event.
Theorem 3. For every computation c, db
! is a process-wise-total partial ordering on Ev(c).
Proof. See Appendix.
By the discussion in Section 4, db
induces a notion CGS db
of CGSs. If g 2 CGS db
the local states in g possibly overlapped in time. For example, Figure 1 shows a computation
c 1 and the lattice hCGS db
-i. The pair of arcs enclosing each event show the endpoints
of the interval timestamp. In the lattice, a node labeled represents the global state in
which process 1 is local state s 1
i and process 2 is in local state s 2
.
4,2

Figure

1: Left: A computation c 1 . Right: The lattice hCGS db
We consider in this paper only detection algorithms with a passive monitor. Each process
in the original system sends its timestamped local states to a new process, called the monitor.
More specifically, when a process executes an event, thereby terminating its current local
state s, the process sends to the monitor a message containing s and the timestamps C(S(s))
and C(T (s)). 8
We consider only on-line detection, in which the monitor detects the property as soon as
possible. Algorithms for off-line detection, in which the monitor waits until the computation
has terminated before checking whether a property holds, can be obtained as special cases.
We consider first algorithms for detecting Poss db
for a restricted class of predicates and then
consider general algorithms for detecting Poss db
and
.
5.1 Algorithms for Poss db
and
db
for Conjunctive Predicates
Garg and Waldecker [13, 14] have developed efficient algorithms for detecting Poss
conjunctive predicates \Phi. A predicate is conjunctive if it is a conjunction of
predicates that each depend on the local state of one process. For example, if x i is a local
variable of process i, then the predicate x 1 conjunctive, and the predicate
not conjunctive. Their algorithms can be adapted in a straightforward way to
detect Poss db
and
, by (roughly) replacing comparisons based on happened-before with
comparisons based on db
!. This yields detection algorithms with worst-case time complexity
O(N 2 E), where E is the maximum number of events executed by any process. The worst-case
time complexity of both algorithms can be reduced to O((N log N)E) by exploiting the
total ordering on numbers.
We start by reviewing Garg and Waldecker's algorithm for detecting Poss hb
conjunctive
predicates. Suppose the predicate of interest is
depends on
8 Several straightforward optimizations are possible. For example, each message might describe only the
differences between consecutive reported local states, rather than repeating the entire local state. Also,
except for the initial local state, it suffices to include with local state s only the timestamp C(T (s)), since
was sent in the previous message to the monitor. Also, for a given predicate \Phi, events that cannot
possibly truthify or falsify \Phi can be ignored.
the local state of process i. Each process i sends to the monitor timestamped local states
satisfying local states not satisfying OE i are not reported. For each process i, the monitor
maintains a queue q i and adds each timestamped local state received from process i to
the end of q i . Let head(q) denote the head of a non-empty queue q. If for some i and j,
is removed from q i . The heads of the queues are repeatedly
compared and sometimes removed in this way, until the heads of the non-empty queues
are pairwise concurrent. At that point, if all the queues are non-empty, then the heads of the
queues form a CGS satisfying \Phi, so the algorithm returns that CGS (thereby indicating that
Poss hb
some queue is empty, then the monitor waits to receive more local states
and then repeats the procedure just described. The worst-case time complexity is O(N 2 E),
because there are O(NE) local states, and each time a local state is removed from q i , the
new head of q i is compared with the heads of the other O(N) queues.
For detection of Poss db
the number of comparisons can be reduced as follows.
Expanding the definition of CGS db
(c), a global state g is consistent iff
Using the fact that for all i, C 2 (T (head(g(i)))) - C 1 (S(head(g(i)))), which follows from TS1
and TS2, one can show that (7) is equivalent to
min
To evaluate (8) efficiently, we maintain two priority queues p 1 and p 2 , whose contents are
determined by the invariants:
I1: For each process i such that q i is non-empty, p 1 contains a record with key C 1 (S(head(q i )))
and satellite data i. p 1 contains no other records.
I2: For each process i such that q i is non-empty, p 2 contains a record with key C 2 (T (head(q i )))
and satellite data hi; ptri, where ptr is a pointer to the record with satellite data i in
contains no other records.
Recall that the operations on a priority queue p include getMin(p), which returns a record
hk; di with key k and satellite data d such that k is minimal, and extractMin(p), which
removes and returns such a record. We also use priority queues with analogous operations
based on maximal key values. Thus, (8) is equivalent to
where k. The negation of (9) is used in the while loop in Figure 2 to check
the heads of the non-empty queues are concurrent. Let PossConjAlg denote the algorithm
in

Figure

2. If a computation satisfies Poss db
returns a CGS satisfying
\Phi.
To analyze the time complexity, recall that an operation on a priority queue containing
records takes O(log n) time. A constant number of such operations are performed for each
local state, so the worst-case time complexity of the algorithm in Figure 2 is O(EN log N ).
Note that the time complexity is independent of the quality of clock synchronization.
The algorithm in [14] for detecting
conjunctive \Phi can be adapted in a similar
way to detect
\Phi for such predicates.
On receiving x from process i:
add records for i to p 1 and p 2 , to maintain invariants I1 and I2;
while
remove record for i (i.e., record \Lambdaptr ) from
add records for i to p 1 and p 2 , to maintain invariants I1 and I2;
endif
endwhile
return the CGS hhead(q 1
endif
endif

Figure

2: Algorithm PossConjAlg(\Phi) for detecting Poss db
conjunctive predicates. Process
i sends to the monitor only local states satisfying its local predicate.
5.2 General Algorithm for Poss db
We develop an on-line detection algorithm for Poss
db
\Phi by adapting Alagar and Venkatesan's
algorithm for detecting Poss hb
\Phi in non-terminating (i.e., infinite) computations [1]. Their
algorithm is based on their procedure for depth-first search of a lattice of CGSs. A depth-first
exploration of the lattice of CGSs for an infinite computation would never backtrack and
thus would never visit some CGSs near the beginning of the lattice. So, in their algorithm,
the lattice is divided into a sequence of sublattices L corresponding to increasing
prefixes of the computation, and depth-first search is used to explore each sublattice L i+1 \GammaL i .
The following paragraphs describe how to adapt their algorithm to on-line detection of
Poss
db
Finding the initial CGS. In the asynchronous setting, the initial CGS simply contains
the initial local state of each process. In the timed setting, that global state might not be
consistent, since the processes might have been started at different times.
Theorem 4. For every computation c, if CGS ,! (c) is not empty, then hCGS ,! (c); -i contains
a unique minimal element, i.e., c has a unique initial CGS.
Proof. The existence of minimal elements in the lattice of CGSs follows immediately from
non-emptiness and the absence of infinite descending chains in - [7, chapter 2]. We prove
by contradiction that the lattice of CGSs has a unique minimal element. Suppose CGSs g 1
and g 2 are minimal and g 1 6= g 2 . Let -G denote the meet operation of the lattice of CGSs.
Note that g 1 6- g 2 (by the assumptions that g 2 is minimal and g 1 6=
(by the definition of -G ), so (g 1 -G By definition of -G , (g 1 -G
together with (g 1 -G contradicts the assumed minimality of g 1 .
To find the initial CGS, we exploit the fact that for every conjunctive predicate \Phi, if a
computation satisfies Poss db
\Phi, then PossConjAlg(\Phi) finds and returns the unique minimal
CGS satisfying \Phi; the proof of this is closely analogous to the proof of the corresponding
property of Garg and Waldecker's algorithm [14]. A corollary is: if CGS db
(c) is not empty,
then PossConjAlg(true) returns the initial CGS (otherwise, PossConjAlg(true) never calls
return).
Choosing the sequence of sublattices. To avoid delays in detection, when the monitor
receives a timestamped local state, it constructs the largest CGS g 2 that can be constructed
from the local states it has received so far; this is done by the while loop in Figure 4. This
CGS implicitly defines the next sublattice contains exactly the CGSs g such that
denote the CGS constructed when the previous local state was received,
i.e., the CGS corresponding to sublattice L i . After constructing g 2 , the monitor does a
depth-first search of the sublattice L (by definition) contains CGSs g such
that
Exploration of a sublattice. There are two main steps in the exploration of the sublattice
of CGSs between a CGS g 1 and a larger CGS
ffl Use a procedure initStates(g to compute the set S of minimal (with respect to -)
CGSs in that sublattice.
ffl For each CGS g in S, use a procedure depthFirstSearch(g; to do a depth-first
search starting from g of a fragment of that sublattice. These searches together explore
the entire sublattice.
Alagar and Venkatesan observed that initStates can be computed efficiently as follows. For
a local state s, let minstate(s) be the unique minimal CGS containing s, and let succ(s) be
the local state that occurs immediately after s on the same process (if there is no such local
state, then succ(s) is undefined). Then initStates(g
procedure
var
for
endif
return S
Computing minstate. Our algorithm for computing minstate is similar to our algorithm
for computing the initial CGS. It relies on the following property of PossConjAlg: if PossConjAlg(\Phi)
is started from a global state g (i.e., for all i, local states of process i that occur before g(i) are
ignored), and if the remainder of the computation satisfies Poss db
finds the unique minimal CGS greater than g and satisfying \Phi. For a global state g and a
local state s, let g[i 7! s] denote the global state that is the same as g except that the local
state of process i is s. A simple way to compute minstate(s) is to call PossConjAlg(true)
starting from the global state g 0 [pr(s) 7! s], where g 0 is the initial CGS. An optimization
is sometimes possible. Consider a call minstate(s 2 ). If minstate has not previously been
called with a local state of pr(s 2 ) as argument, then the optimization does not apply, and
minstate is computed as described above. Otherwise, let s 1 be the argument in the previous
call to minstate on a local state of pr(s 2 ). Observe that s 1 occurred before s 2 , because: (1)
minstate is called only from initStates, and initStates is called on a non-decreasing chain
of CGSs (this is a property of the algorithm in Figure 4 below), and (2) (assuming short-circuiting
evaluation of - in initStates) initStates(g
PossConjAlg(true) from global state minstate(s 1 )[pr(s) 7! s] instead of g 0 [pr(s) 7! s]. This
leads to the following algorithm. For each i, old(i) contains the result of the previous call to
minstate on a local state of process initially, old(i) is set to g 0 .
procedure
old(pr(s)) := the CGS returned by PossConjAlg(true) started from old(pr(s))[pr(s) 7! s];
return
Depth-first search of fragment of sublattice. Since a CGS may have multiple predecessors
in the lattice of CGSs, the search algorithm needs (for efficiency) some mechanism to
ensure that each CGS is explored only once. A straightforward approach is to maintain a set
containing the CGSs that have been visited so far. However, this may be expensive in both
space and time. Alagar and Venkatesan [1] proposed the following clever alternative. Introduce
a total ordering ! idx
on CGSs, defined by:
lexicographically
smaller than index(g 2 ), where for a global state g, index(g) is the tuple hk
that g(i) is the k i 'th local state of process i. During the depth-first search, explore a CGS g
only from the immediate predecessor (with respect to -) of g that is maximal (among the
immediate predecessors of g) with respect to ! idx . This leads to the algorithm in Figure 3,
where for a CGS g, pred(g) is the set of immediate predecessors of g in the lattice of CGSs.
To compute pred(g): for each process i, check whether moving process i back by one local
state yields a CGS, and if so, include the resulting CGS in the set.
Putting these pieces together yields the on-line detection algorithm in Figure 4. All local
states "after" g 0 (i.e., local states s such that g 0 (pr(s)) occurs before s) are handled by the
"On receiving s from process i" statement, even though some of these local states might
have been received before the initial CGS was found.
Recall that a process sends a local state to the monitor when that local state ends. This
is natural (because / db
! depends on when local states end) but can delay detection. One
approach to bounding and reducing this delay is for a process that has not reported an event
to the monitor recently to send a message to the monitor to report that it is still in the same
local state (as if reporting execution of skip). Another approach, described in [23], requires
a bound on message latency: at each instant, the monitor can use its own local clock and
this bound to determine a lower bound on the ending time of the last local state it received
from a process.
5.2.1 Complexity
To analyze the time complexity, we consider separately the cost of all invocations of minstate
and the cost of all other operations. In effect, for each process, the calls to minstate cause
PossConjAlg algorithm to be executed N times (once for each process) on (at worst) the
procedure depthFirstSearch(g;
if \Phi(g) then
return(true)
else
for
if g(i) 6= g 2 (i) then
if consis db
if g is maximal in hS; ! idx
return(true)
endif
endif
rof
return(false)

Figure

3: Algorithm for depth-first search.
computation. Thus, the total cost of calls to PossConjAlg from minstate, and hence
the total cost of calls to minstate, is O(EN 2 log N ). The total cost of all executions of
the while loop in Figure 4 is O(EN 3 ), since: (1) evaluating the loop condition takes time
O(N 2 ), and the condition is evaluated at most once for each of the O(NE) local states;
(2) the loop body is executed at most once for each of the O(NE) local states, and each
execution takes constant time. The total cost of all executions of the body of the for loop in

Figure

4 is O(jCGS
db
since the depth-first search takes O(N 2 ) time per CGS, since
evaluating pred takes O(N 2 ) time. Each call to initStates takes O(N 3 (excluding the
cost of calls to minstate), because: (1) evaluating - takes O(N) time, and (2) - may be
evaluated O(N 2 ) times, because of the for loop and the existential quantifier. The total
cost of all calls to initStates is O(N 4 E), since initStates is called at most once per local
state. Summing these contributions, we conclude that the worst-case time complexity of the
algorithm is O(jCGS db
(c)j depends on the rate at which events occur relative to the error between clocks.
To simplify the complexity analysis, suppose: (1) the interval between consecutive events
at a process is at least - , (2) the error between clocks is known to be at most ", and (3)
the interval timestamp on an event e is given by C 1
t is the value of the local clock of machine pr(e) when e occurred. Then, for every event
Initialization Phase :
0 := the CGS returned by PossConjAlg(true); (  g 0 is the initial CGS  )
For all local states s such that g 0 (pr(s)) occurs before s:
On receiving s from process i:
while
largest CGS  )
for s in initStates(g
report Poss
db
\Phi and exit
endif
rof

Figure

4: Algorithm for detecting Poss db
e, each local state is concurrent with at most 3 local
states of each other process, so each local state is in at most O(3 N \Gamma1 ) CGSs, so there are
O(3 N E) CGSs, so the worst-case time complexity of the algorithm is O(3 N EN 2 ). If - 2",
then each local state is concurrent with at most d(4" local states of each other
process, so there are O((d4"=-e E) CGSs, so the worst-case time complexity of the
algorithm is O((d4"=-e In both cases, the worst-case time complexity of
detecting Poss db
is linear in E, which is normally much larger than N ; in contrast, the
worst-case time complexity of general algorithms for detecting Poss
and
A more realistic complexity analysis requires considering distributions of inter-event
times, rather than simply fixing a minimum value. Specifically, we consider distributed
computations with inter-event times selected from a normal (i.e., Gaussian) distribution
with mean - and standard deviation p - (negative numbers selected from the distribution
were ignored). For simplicity, we continue to assume a fixed bound " on the error between
clocks. The number of CGSs then depends on N , E, and the ratio -=". As in the cases
analyzed above, the number of CGSs scales linearly with E; this is illustrated by the graph
in

Figure

5. Figure 6 plots the number of CGSs vs. -=" and N . One can see that when -="
is large, the number of CGSs increases slowly (roughly linearly) with N ; when -=" is small,
the number of CGSs increases exponentially with N .
#CGSs

Figure

5: Number of CGSs vs. E, for
mu/epsilon
mu/epsilon
#CGSs

Figure

Left: Number of CGSs vs. -=" and N , for ranging from 6 to
50. Right: Number of CGSs vs. -=" and N , for with -=" from 2 to 50. Note that
the vertical scales in these two graphs are very different.
5.3 General Algorithm for
The detection algorithm for
\Phi in [6, 23] can be adapted to detect
\Phi by (roughly)
replacing each condition of the form e 1
db
That algorithm divides the lattice
into levels. The level of a local state in a local computation is the number of local states
preceding it in that computation. The level of a global state g is the sum of the levels of
the constituent local states. Level ' of the lattice of CGSs contains the CGSs with level
'. Following [6, 23], we give an algorithm in which the monitor constructs one level of the
lattice of CGSs at a time. Constructing one level of the lattice at a time is unnecessary
and sometimes delays detection of a property; this construction is used only to simplify the
presentation.
The algorithm used by the monitor to detect
\Phi is given in Figure 7. The lowest level
of the lattice contains only the initial CGS. The while loop maintains the following invariant:
last contains CGSs that are reachable from the initial CGS without passing through a CGS
satisfying \Phi. In line (y) of the algorithm, the monitor considers each global state g in
last and each process i, and checks whether the local state succ(g(i)) is concurrent with
the local states in g of all the other processes. (The monitor waits for the local states
they have not already arrived.) If so, the monitor adds g[i 7!
succ(g(i))] to current if it is not already in current .
:= the CGS returned by PossConjAlg(true); (  find the initial CGS  )
last := fgg;
remove all CGSs in last that satisfy \Phi;
while last
current := CGSs that are immediate successors of CGSs in last ; (y)
remove all CGSs in current that satisfy \Phi;
last := current ;
report

Figure

7: Algorithm for detecting
db
Since \Phi could be false in all CGSs, and because we assume that the cost of evaluating
\Phi on each global state is a constant, the worst-case asymptotic time complexity of this
algorithm equals the worst-case asymptotic time complexity of constructing CGS db
. For
each CGS, the algorithm advances each of the N processes and, if the resulting global state
g is consistent, the algorithm checks whether g is already in current . Let Tm denote the total
cost of these membership checks; then constructing CGS db
(c) takes \Theta(jCGS db
time. Tm depends on the data structure used to implement current . With a naive array-based
implementation, each check has constant cost, so Tm is \Theta(E N ), due to the cost of
initializing the arrays, so the worst-case time complexity of the algorithm is \Theta(E N N 2 ). 9
However, this implementation has a serious disadvantage: the time complexity remains
even if the actual number of CGSs is much smaller than E N , which is typically the
case. Thus, generally preferable alternatives are to implement current as a dictionary, using
a hash table or balanced trees. Let W (c) be the width of the lattice CGS db
(c), i.e., the
maximum size of a level of that lattice. If balanced trees are used, each membership check
has cost O(log W (c)), so the worst-case time complexity is O(jCGS db
Both jCGS db
(c)j and W (c) depend on the rate at which events occur relative to the error
between clocks. To simplify the complexity analysis, we introduce - and ", with the same
meanings as in Section 5.2.1. If - ? 2", then there are O(3 N E) CGSs (as above), and W (c)
is O(3 N ), so the worst-case time complexity of the algorithm is O(3 N EN 2 ). If - 2", then
there are O((d4"=-e E) CGSs (as above), and W (c) is O((d4"=-e
worst-case time complexity is O((d4"=-e In both cases, the
worst-case time complexity of detecting
is linear in E; in contrast, the worst-case time
complexity of general algorithms for detecting
For a more realistic complexity analysis, we consider the same distribution of inter-event
times and the same bound on error between clocks as in the last paragraph of Section 5.2. Of
course, the number of CGSs is still characterized by Figures 5 and 6. It is easy to argue that
under these assumptions, the expected size of each level is independent of E and depends
in the same fashion as the number of CGSs on -=" and N . Thus, graphs showing the
dependence of W (c) on -=" and N would have the same shape as the graphs in Figure 6.
6 Detection Based on a Weak Event Ordering: Inst
The "possibly occurred before" ordering on events is defined
pb
db
Using (3), this induces a relation / pb
on local states, with the interpretation: s / pb
s possibly ended before s 0 started. Two local states are strongly concurrent if they are not
related by / pb
local states must overlap in time. We call elements of CGS pb
strongly
consistent global states (SCGSs). 10 For example, Figure 8 shows hCGS pb
recall that
computation c 1 is shown in Figure 1. Note that hCGS pb
is a total order. More
generally, we can show:
Theorem 5. For all computations c, hCGS pb
is a total order and therefore a lattice.
9 In on-line detection, E is not known in advance, so the arrays may need to be resized (e.g., doubled)
occasionally. This does not change the asymptotic time complexity.
Fromentin and Raynal call elements of CGS
inevitable global states [9].

Figure

8: The lattice hCGS pb
Proof. Suppose not, i.e., suppose there exist a computation c, two global states
CGS pb
(c), and two processes i and j such that g(i) / pb
g(j). By definition
of CGS pb
definition of CGS pb
so by transitivity,
so by transitivity, C 2 which is a contradiction.
It follows that Poss pb
and
are equivalent, i.e., for all computations c and predicates
\Phi, c satisfies Poss pb
pb
\Phi. We define Inst ("instantaneously") to denote
this modality (i.e., Poss
pb
and
pb
Informally, a computation satisfies Inst \Phi if there
is a global state g satisfying \Phi and such that the system definitely passes through g during
the computation.
Theorem 1 does not apply to pb
!, because:
Lemma 6. pb
! is not a partial ordering.
Proof. Consider the computation in Figure 9. The actual orderings between e 2
2 and e 1
2 and
between e 2
2 and e 1
3 cannot be determined from the interval timestamps, so e 1pb
2 and
e 2pb
2 . Since also e 1pb
contains a cycle.
In light of this, it is not surprising that a minimal increase in hCGS pb
does not necessarily
correspond to advancing one process by one event. For example, consider the computation
c 1 in

Figure

1. As shown in Figure 8, two processes advance between the the second and
third SCGSs of c 1 . In some computations, a minimal increase hCGS pb
corresponds
to an advance of multiple events per process. Such a computation c 2 is shown in Figure 9.
There is no local state of process 2 with which s 1
definitely overlaps, so s 1
2 is not part of any
SCGS, and process 1 advances by two events between consecutive SCGSs of c 2 . Computation
c 2 has only two SCGSs: hs 1
Since a minimal increase in hCGS pb
does not necessarily correspond to advancing
one process by one event, the algorithms in Section 5 cannot be adapted easily to detect Inst.
Our algorithm for detecting Inst is based on Fromentin and Raynal's algorithm for detecting
Properly in asynchronous systems [9, 10]. The definition of Properly, generalized to an
arbitrary ordering on events, is:
e 2e 1e 2e 1e 1e 1e 2s 2s 2s 1s 1s 1
Figure

9: A computation c 2 .
Properly: A computation c satisfies Properly ,! \Phi iff there is a global state satisfying
\Phi and contained in every path of hCGS ,! (c); -i.
Theorem 7. Properly db
is equivalent to Inst.
Proof. It suffices to show that a global state g is in CGS pb
(c) iff it is contained in every
maximal path of CGS db
(c). The proof is based on Theorem IGS of [9], which states that
a global state g is contained in every maximal path of hCGS hb
last returns the last element of a sequence. A closely analogous
proof shows that a global state g is contained in every maximal path of hCGS db
which by definition of db
is equivalent to
The only significant difference involves the last local state of each process. Informally, the
disjunct needed in Fromentin and Raynal's analysis because the global
state g f containing the last local state of each process appears in every maximal path of
even though the system might not pass through g f in real-time, since the
processes might terminate at different times. This peculiarity does not arise when real-time
timestamps are used, so (11) does not need a disjunct dealing specially with the last local
state of each process. Expanding the definition of CGS pb
(c) and simplifying yields (11).
As an example of this equivalence, note that hCGS pb

Figure

8 contains exactly
the CGSs that are contained in every path of hCGS db

Figure

1.
A straightforward adaptation of Fromentin and Raynal's algorithm for detecting Properly hb
yields an algorithm for detecting Inst with worst-case time complexity O(N 3 E) (the same
as Fromentin and Raynal's algorithm). Optimizations similar to those presented in Section
5.1 reduce this to O((N log N)E). Expanding the definition of CGS pb
(c), a global state g is
strongly consistent iff To check this condition
efficiently, we introduce priority queues p 1 and p 2 , whose contents are determined by the
following invariants:
J1: For each process i such that q i is non-empty, p 1 contains a record with key C 1 (T (head(q i )))
and satellite data hi; ptri, where ptr is a pointer to the record with satellite data i in
contains no other records.
J2: For each process i such that q i is non-empty, p 2 contains a record with key C 2 (S(head(q i )))
and satellite data i. p 2 contains no other records.
We use p 1 and p 2 to define a function SC(p efficiently tests whether the heads of
the non-empty queues are pairwise strongly concurrent. Taking into account the possibility
that some i, we obtain
where countMax(p) is the number of records containing the maximal value of the key in
priority queue p, and data(hk; Thus, the following procedure
makeSC ("make Strongly Concurrent") loops until the heads of the non-empty queues are
strongly concurrent:
procedure makeSC ()
while
remove record for i (i.e., record \Lambdaptr ) from
add records for i to p 1 and p 2 to maintain invariants J1 and J2;
endif
endwhile
where extractMin(p) is like getMin except that it removes the record it returns.
The optimized algorithm for detecting Inst appears in Figure 10, where head2(q) returns
the second element of a queue q. When a SCGS g is found, if g does not satisfy \Phi, then
the monitor starts searching for the next SCGS by advancing some process j such that this
advance yields a CGS (i.e., an element of CGS db
). If at first no process can be so advanced
(e.g., if each queue q i contains only one element), then the monitor waits for more local states
to be reported. It follows from the definitions of CGS db
and CGS pb
advancing some
process yields a CGS, then advancing some process j such that C 1 (S(head2(q j ))) is minimal
yields a CGS. Thus, we reduce the time needed to find such a process j by maintaining a
priority queue p 3 satisfying the invariant:
J3: For each process i such that q i is non-empty, p 3 contains a record with key C 1 (S(head2(q j )))
and satellite data i. p 3 contains no other records.
Thus, in line (y), it suffices to take Testing whether g[j 7! head2(q j )] is
consistent can be done in O(log N) time by temporarily updating p 1 and p 2 as if process j
had been advanced and then using (9).
We analyze the worst-case time complexity by summing the times spent inside and outside
of makeSC. Each iteration of the while loop in makeSC takes O(log N) time (because each
operation on priority queues takes O(log N) time) and removes one local state. The computation
contains O(NE) local states, so the total time spent inside makeSC is O((N log N)E).
The total time spent in the code outside makeSC is also O((N log N)E), since there are
O(NE) SCGSs (this is a corollary of Theorem 7), and each local state is considered at most
once and at O(log N) cost in the wait statement. Thus, the worst-case time complexity of
the algorithm is O((N log N)E).
On receiving x from process i:
add records for i to p 1 and p 2 to maintain invariants J1 and J2;
found := true;
while found
makeSC ();
if
found := false
else (  found a SCGS  )
:= the global state (-i: head(q i )); (  g is a SCGS  )
if g satisfies \Phi then
return g
else
wait until there exists j such that g[j 7! head2(q j )] is in CGS db
remove records for j from p 1 and
add records for j to p 1 and p 2 to maintain invariants J1 and J2
endif
endif
endwhile
endif

Figure

10: Algorithm for detecting Inst \Phi.
Applications
7.1 Coherence Protocols
Coherence of shared data is a central issue in many distributed systems, including distributed
file systems, distributed shared memory, and distributed databases. A typical invariant
maintained by a coherence protocol is:
one machine has a copy of a data item in write mode, then no other machine
has a valid copy of that data item.
As part of testing and debugging a coherence protocol, a monitor might be used to issue
a warning if Poss db
:cohrnt is detected and report an error if
:cohrnt is detected.
A computationally cheaper but sometimes less informative alternative is to monitor only
Inst :cohrnt and report an error if it is detected.
A detection algorithm based on happened-before could be used instead, if the system can
be modified to maintain vector clocks (or for some reason maintains them already). However,
if the coherence protocol uses timers, then time acts as a hidden channel [2] (i.e., a means
of communication other than messages), so detection based on happened-before might yield
less accurate results. Timers can be used in coherence protocols to:
ffl obtain a lock, by broadcasting a request for a lock and, if no conflicting announcement
is received within an appropriate time interval, granting oneself the lock.
ffl release a lock, by associating a finite lifetime with the lock; such a lock is called a lease
[15]. When the lifetime expires, all processes know (without further communication)
that the lock has been released.
For example, the resource allocation algorithm in [19, Section 5.1] uses timers in both of these
ways. These techniques use timers (instead of messages) for synchronization, so detection
based on happened-before is less appropriate. For example, release of a lock by one process
and acquisition of that lock by another process need not be related by happened-before, so
Poss hb
:cohrnt may be detected even when coherence was maintained and Poss db
:cohrnt
would not be detected.
Clock-based monitoring is useful even for coherence protocols that provide weaker guarantees
than cohrnt . For example, in the Sun Network File System (NFS) [29, Section 17.6.2],
file information is cached. Timers are used to limit staleness: if the cached information is
needed again after the timer expires, the client asks the server whether the cached information
is still valid. Since this lock-free approach does not enforce the one-copy file-sharing
semantics that is traditional in UNIX, it is useful to monitor the system to detect how often
violations of one-copy semantics are seen by applications. For example, the detection algorithm
for Inst can easily be adapted to count (instead of just detect) SCGSs satisfying the
predicate: some process is reading cached information and some other cache contains a more
recent version of that information. In NFS, the lifetime of cached data is typically tens of
seconds, which is three orders of magnitude larger than typical clock synchronization error
in a LAN, so this approach should detect most violations of one-copy semantics.
7.2 Concurrency Control for Distributed Transactions
Leases can also be used for concurrency control in distributed database systems, to reduce
the number of messages needed to commit read-only transactions, as described in [22, Section
7]. The idea is that a read-only transaction acquires leases as it uses data objects. If the
transaction completes before any of those leases expires, then the coordinator commits the
transaction, without further communication. As part of testing and debugging such a system,
one might use a monitor to detect violations of the invariant: when a transaction commits,
it holds locks on all of the objects it uses. Since commit events and expirations of leases may
be unrelated by happened-before, detection based on Poss hb
or
may report violations
even when no violation occurred and detection based on real-time clocks would not report a
violation.



--R

Techniques to tackle state explosion in global predicate detection.


Local and temporal predicates in distributed systems.
Detection of global predicates: Techniques and their limitations.
Consistent detection of global predicates.
Introduction to Lattices and Order.
Reachability analysis on distributed executions.
Inevitable global states: a concept to detect unstable properties of distributed computations in an observer independent way.
Characterizing and detecting the set of global states seen by all observers of a distributed computation.

Efficient detection of channel predicates in distributed systems.
Detection of weak unstable predicates in distributed programs.
Detection of strong unstable predicates in distributed programs.
An efficient fault-tolerant mechanism for distributed file system consistency
Detecting atomic sequences of predicates in distributed computations.
Linear space algorithm for on-line detection of global predicates

Using time instead of timeout in fault-tolerant systems
The mutual exclusion problem: Part i-a theory of interprocess com- munication
On interprocess communication: Part 1.
Practical uses of synchronized clocks in distributed systems.
Detection of global state predicates.
time synchronization: the Network Time Protocol.
Network time protocol (version specification
Improved algorithms for synchronizing computer network clocks.

Detecting causal relationships in distributed computations: In search of the holy grail.
Operating System Concepts.
Detecting global predicates in distributed systems with clocks.
Efficient symbolic detection of global properties in distributed systems.
Faster possibility detection by combining two approaches.

--TR
Using Time Instead of Timeout for Fault-Tolerant Distributed Systems.
The mutual exclusion problem
Leases: an efficient fault-tolerant mechanism for distributed file cache consistency
Practical uses of synchronized clocks in distributed systems
Consistent detection of global predicates
Introduction to OSF DCE (rev. 1.0)
Detecting atomic sequences of predicates in distributed computations
Local and temporal predicates in distributed systems
Improved algorithms for synchronizing computer network clocks
Specification and verification of dynamic properties in distributed computations
Detection of Strong Unstable Predicates in Distributed Programs
Shared global states in distributed computations
Efficient detection of channel predicates in distributed systems
Efficient Distributed Detection of Conjunctions of Local Predicates
Consistent global states of distributed systems
Real-time communication
Time, clocks, and the ordering of events in a distributed system
Operating System Concepts, 4th Ed.
Detection of Weak Unstable Predicates in Distributed Programs
Detection of Global State Predicates
Faster Possibility Detection by Combining Two Approaches
Detecting Global Predicates in Distributed Systems with Clocks
Reachability Analysis on Distributed Executions
Techniques to Tackle State Explosion in global Predicate Detection
Efficient Symbolic Detection of Global Properties in Distributed Systems
Global predicates in rough real time
Characterizing and Detecting the Set of Global States Seen by all Observers of a Distributed Computation

--CTR
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
real-time monitoring;global predicate detection;distributed debugging;consistent global states