In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 185-199. Springer, September 1997.
Abstract: This paper proposes a framework for predicate detection in systems of processes with approximately-synchronized real-time clocks. Timestamps from theses 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 (`possibly held') , Def (`definitely held'), and Inst (`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.
Keywords: global predicate detection, consistent global states, partially-synchronous systems, distsributed debugging, real-time monitoring.