The Decentralized Non-Blocking Atomic Commitment Protocol

In a transactional system, an atomic commitment protocol ensures that for any transaction, all data managers agree on the same outcome: commit or abort. A non-blocking atomic commitment protocol enables an outcome to be decided at every correct data manager despite the failure of others. It is well known that the famous Two Phase Commit protocol (2PC) is a blocking protocol, whereas the Three Phase Commit protocol (3PC) is a non-blocking protocol. Both protocols are centralized. In this paper, we discuss a Decentralized Non-Blocking Atomic Commitment protocol, named DNB-AC. In the absence of failures, the DNB-AC protocol requires the same number of steps to commit than the 2PC protocol (three steps). Performance measures show that the DNB-AC protocol is significantly faster that the 3PC and, in the case of a broadcast network, is almost as efficient as the 2PC. The DNB-AC protocol uses a uniform consensus protocol as a termination protocol. Using the recent results by Chandra and Toueg on solving consensus in an asynchronous system augmented with unreliable failure detectors, we give a precise characterization of the liveness of DNB-AC. We show that DNB-AC is non-blocking when a majority of data managers are correct and the failure detector is of class $\Diamond {\cal S}$.