TY - GEN
T1 - Detecting Global Predicates in Distributed Systems with Clocks
AU - Stoller, Scott D.
N1 - Publisher Copyright:
© 2015, Springer Verlag, All Rights Reserved.
PY - 1997
Y1 - 1997
N2 - 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.
AB - 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.
KW - Consistent global states
KW - Distributed debugging
KW - Global predicate detection
KW - Partially-synchronous systems
KW - Real-time monitoring
UR - https://www.scopus.com/pages/publications/84949218321
U2 - 10.1007/bfb0030684
DO - 10.1007/bfb0030684
M3 - Conference contribution
AN - SCOPUS:84949218321
SN - 3540635750
SN - 9783540635758
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 199
BT - Distributed Algorithms - 11th International Workshop, WDAG 1997, Proceedings
A2 - Mavronicolas, Marios
A2 - Tsigas, Philippas
PB - Springer Verlag
T2 - 11th International Workshop on Distributed Algorithms, WDAG 1997
Y2 - 24 September 1997 through 26 September 1997
ER -