Non-blocking atomic commit in asynchronous distributed systems with failure detectors

This paper addresses the Non-Blocking Atomic Commit (NB-AC) problem in asynchronous distributed systems augmented with failure detectors. We first show that, in these systems, NB-AC and Consensus are incomparable. Roughly speaking, there is a failure detector that solves NB-AC but not Consensus and a failure detector that solves Consensus but not NB-AC. Then we introduce the Anonymously Perfect failure detector ?P. We show that, to solve NB-AC, ?P is necessary (while P is not), whereas ?P + lozengeS is sufficient when a majority of the processes are correct. We draw from our results some observations on the practical solvability of NB-AC.