On the Hardness of Failure-Sensitive Agreement Problems

In [CT96], [FRT99], and [SM95], respectively, it was stated that the weakest failure detector for any of non-blocking atomic commit, terminating reliable broadcast and leader election, is the Perfect failure detector P. This paper presents a counter example of those results.We exhibit a failure detector that is incomparable to P, and yet solves those problems.