A Fundamental problem in developing distributed software is that no pr
ocess has access to the global state. Thus, computing a global predica
te or function-a need that occurs frequently in many distributed syste
ms-typically requires significant programming. Being able to observe a
distributed computation is useful for many fundamental problems in di
stributed software, such as debugging, testing, and fault-tolerance. A
fter ? program is debugged and tested, it must be monitored for fault-
tolerance, again requiring something that will observe the global stat
e. Finally, the ability to observe global predicates generalizes algor
ithms for many previous problems such as detecting program termination
, token loss, and deadlock. Research on how to detect global predicate
s has yielded three sets of algorithms. In the global snapshot algorit
hm, global snapshots of the computation are repeatedly computed until
the desired predicate becomes true. However, this approach works only
for stable predicates like deadlock and termination, which do not turn
false once they become true. In the second set of algorithms, a latti
ce of global states is constructed. Unlike the global snapshot approac
h, this approach lets users detect unstable predicates. How ever, it c
an mean exploring a prohibitive number of global states. This article
surveys algorithms that use a third approach, which exploits the struc
ture of the predicate, but does not build a lattice. Instead, they exa
mine the computation itself to deduce if a predicate became rme. These
algorithms are computationally efficient and can be used to detect ev
en unstable predicates.