A knowledge theoretic analysis of atomic commitment protocols

Vassos Hadzilacos

Recently a new theory of distributed computing has been proposed, according to which a distributed computation is viewed as an activity of knowledge acquisition and dissemination by communicating processes (Halpern and Moses [1986], Halpern and Fagin [1985]). In this paper, we use the knowledge formalism to analyse atomic commitment protocols employed by transactions in distributed database systems, such as two-phase commit. We characterise the two-phase commit and three-phase commit families of protocols in terms of the level of knowledge that must be acquired by a site to commit a transaction. We show that in the two-phase commit protocol the decision to commit is reached with the minimum knowledge necessary under any atomic commitment protocol; and that in the three-phase commit protocol the decision to commit is reached with the minimum knowledge necessary under any non-blocking atomic commitment protocol. Our analysis also provides a proof of the fact that there is no non-blocking atomic commitment protocol that can tolerate communication failures (a result anticipated in the work of Gray --- cf. his ``Generals' Paradox'' [1978] --- and formally proved by Skeen [1982] for a model of computation less general than the one used here). Finally, using knowledge theory, we derive a lower bound for the number of messages needed to commit a transaction (a previously known result, due to Dwork and Skeen [1983]). This lower bound is optimal in that it is matched by the number of messages used by a well-known protocol, the linear (or nested) two-phase commit.