On the Weakest Failure Detector for Hard Agreement Problems

M. Larrea (Spain)


Fault Tolerance, Failure Detector, Agreement.


Chandra and Toueg [J. ACM 43 (2)(1996)] and Fromentin et al. [Proc. IEEE Internat. Conf. on Distrib. Comput., 1999], respectively, stated that the weakest failure detector for any of Non-Blocking Atomic Commitment and Terminating Reliable Broadcast is the Perfect failure detector P. Recently, Guerraoui [IPL 79 (2001)] presented a counterexample of those results, exhibiting a failure detector called Marabout (M) that is incomparable to P and yet solves those problems. In this paper we present three new perfect failure detector classes as alternatives to P and M. All our classes are weaker than P. Furthermore, two of them are also weaker than M, and yet solve Non-Blocking Atomic Commitment and Terminating Reliable Broadcast. Interestingly, our failure detector classes are implementable whenever P is implementable (e.g., in a synchronous system), which is not the case with M.

Important Links:

Go Back