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.
Scott Stoller's Home Page