An efficient communication structure for distributed commit protocols

To maintain consistency in a distributed database environment, the transactions must be executed atomically. The standard algorithm for ensuring an atomic execution is called the distributed commit protocol. The two-phase commit protocol and its variations, the well-known protocols used for this purpose, are characterized by successive rounds of message exchange, among all the sites of the database, at the time a transaction enters into a completion phase. The performance of these protocols is given by a complexity measure that depends on the communication structure of the protocol. Given N sites, the worst-case complexity of a commit protocol is O(N/sup 2/). A communication structure called maximal binomial structure (MBS) is presented, for which the complexity of the protocol is O(N*log/sup 3/ N). A lower bound for this complexity is also given, which is O(N*log/sup 2/ N). Protocols using the MBS remain symmetric. A scheme for an arbitrary expansion of the MBS to allow communication among a large number of sites is proposed. For the expanded system, the protocol complexity is also shown to be O(N*log/sup 3/ N). These structures are shown to be superior to other known structures.<>