Increasing the Resilience of Atomic Commit, at No Additional Cost

This paper presents a new atomic commitment protocol that always allows a quorum in the system to make progress. Previously suggested quorum-based protocols (e.g. [12]) allow a quorum to make progress in case of one failure. If failures cascade, however, and the quorum in the system is "lost" (i.e. at a given time no quorum component exists, e.g. because of a total crash), a quorum can later become connected and still remain blocked. The importance of this work is in demonstrating, using a simple algorithm, how protocols that always allow a majority to make progress can be constructed. 1 Introduction Reliability and availability of loosely coupled distributed database systems is becoming a requirement for many installations, and fault-tolerance is becoming an important aspect of distributed systems design. When processors crash, or when communication failures occur, it is desirable to allow as many processors as possible to make progress. In this paper we present a novel atomic comm..