On the weakest failure detector for hard agreement problems ?
Chandra and Toueg [J. ACM 43 (1996) 225] and Fromentin et al. [Proc. IEEE Internat. Conf. on Distrib. Comput., 1999, p. 470], 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) 99] 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.
failure detector atomic commit terminating reliable broadcast distributed computing fault-tolerance consensus