# Detecting Global Predicates in Distributed Systems with Clocks

## Abstract:

This paper proposes a framework for predicate detection 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: $\Poss_T\Phi$ ($\Phi$ possibly held''), $\Def_T\Phi$ ($\Phi$ definitely held''), and $\Inst\Phi$ ($\Phi$ definitely held at a specific instant''). This paper defines these modalities and gives efficient algorithms for detecting them; the algorithms are based on algorithms of Cooper and Marzullo, Garg and Waldecker, and Fromentin and Raynal.