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
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .