# Detecting Global Predicates in Distributed Systems with Clocks

## Abstract:

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 {\it detection modalities}, \ie, 3 meanings of predicate $\Phi$ held during a computation'', namely: $\PossR\Phi$ ($\Phi$ possibly held''), $\DefR\Phi$ ($\Phi$ definitely held''), and $\Inst\Phi$ ($\Phi$ 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.