TITLE :

Distributed predicate detection in a faulty environment


AUTHORS :


Vijay K. Garg
Department of Electrical and Computer Engineering,
The University of Texas at Austin,
Austin, TX 78712.

J. R. Mitchell
Department of Electrical and Computer Engineering,
The University of Texas at Austin,
Austin, TX 78712.

ABSTRACT :

There has been very little research in distributed predicate detection
for faulty, asynchronous environments.  In this
paper we define a class of predicates called {\em set decreasing} predicates
which can be detected in such an environment.  We introduce a 
set of failure detectors called infinitely often accurate detectors
which are implementable in asynchronous systems.
Based on these failure detectors we present an algorithm to
detect conjunction of local predicates and send-monotonic channel predicates.
Since perfect failure detection is impossible in an asynchronous system,
we cannot guarantee that our detection algorithm will not have
false detections. However, if the predicate ever holds then it is
guaranteed to be detected.  


KEYWORDS :

Predicate Detection, IO Failure Detector, Channel Predicates, Fault-Tolerance