language: en

Detecting Global Predicates in Distributed Systems with Clocks

Scott D. Stoller
Dept. of Computer Science, Indiana University,
Bloomington, IN 47405, USA
February 7, 2000

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 detection modalities, i.e., 3 meanings of "predicate held during a computation", namely: Poss T (" possibly held"), Def T (" 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, distributed debugging, real-time monitoring

1 Introduction