TI THE COMMUNICATION COMPLEXITY OF ATOMIC COMMITMENT AND OF
GOSSIPING 

LT CUCS-499-89 

OR COLUM 

YR 1989 

AU Ouri Wolfson 

AB 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 complity, 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 variations of the two-phase commit
protocol.