Observation of Global Properties in Distributed Systems

Observation of global properties of a distributed program is required in many applications such as debugging of programs and fault-tolerance in distributed systems. I present a survey of algorithms for observing various classes of global properties. These properties include those possibly true in a computation, definitely true in a computation and those based on the control flow structure of the computation. 1 Introduction One of the fundamental problems in development of distributed software is that no process has access to the global state. Consequently, computation of any global predicate or a function requires a non-trivial programming effort. For example, consider a distributed debugging system. The detection of global predicate arises in implementing the most basic command of a debugging system:"stop the program when the predicate q is true." To stop the program, it is necessary to detect the predicate q; a non-trivial task if q requires access to the global state. There have be..