Portal de Periódicos da CAPES

Detecting global predicates in distributed systems with clocks

1997; Springer Science+Business Media; Linguagem: Inglês

10.1007/bfb0030684

1611-3349

Scott D. Stoller,

Software System Performance and Reliability

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: POSST Ф ("Ф possibly held"), DefT Ф ("Ф 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.