This paper investigates the amount of information about failures needed to solve the predicate detection problem in asynchronous systems with crash failures. In particular, we show that predicate detection cannot be solved with traditional failure detectors, which are only functions of failures. In analogy to the definition of failure detectors, we define a failure detection sequencer, which can be regarded as a generalization of a failure detector. More specifically, our failure detection sequencer Sigma outputs information about failures and about the final state of the crashed process. We show that Sigma is necessary and sufficient to solve predicate detection. Moreover, Sigma can be implemented in synchronous systems. Finally, we relate sequencers to perfect failure detectors and characterize the amount of knowledge about failures they additionally offer.
This is the extended version (including the appendices) of the paper which appeared in "Distributed Computing," vol. 2508 of Lecture Notes in Computer Science (Springer, Berlin Heidelberg, 2002), pp. 280-294.
By: F.C. Gärtner and S. Pleisch
Published in: RZ3438 in 2002
Questions about this service can be mailed to reports@us.ibm.com .
