1989 Reports

The Communication Complexity of Atomic Commitment and of Gossiping

Wolfson, Ouri; Segall, Adrian

We consider the problem of atomic commitment of a transaction in a distributed database. This is a variant of the famous gossiping problem (see [HHL] for a survey). Given a set of communication costs between pairs of participant sites, we establish that the necessary communication cost for any atomic commitment algorithm is twice the cost of a certain minimum spanning tree. We also establish the necessary communication time for any atomic commitment algorithm, given a set of communication delays between pairs of participant sites, and the time at which each participant completes its subtransaction. Then we determine that both lower bounds are also upper bounds in the following sense. There is an efficient (i.e. polynomial-time) algorithm that, in the absence of failures, has a minimum communication cost. There is another efficient algorithm that, in the absence of failures, has a minimum communication time. However, unless P=NP, there is no efficient algorithm which has a minimum communication complexity, namely, for which the product of communication cost and communication time is minimum. Then we present a simple, linear time, distributed algorithm, called TREE-COMMIT, whose communication complexity is not worse than p times the minimum complexity, where p is the number of participants. Finally, we demonstrate that TREE-COMMIT is superior to the existing variants of the two-phase commit protocol.