A class of optimal decentralized commit protocols
Shyan‐Ming Yuan, Ashok K. Agrawala · 2003
The message complexity of decentralized commit protocols is studied. It is shown that O(kNN/sup 1/k/) messages are necessary if only k rounds of message interchanges are allowed. It is also shown that O(Nln N) is a message lower bound for any decentralized commit protocol. A class of decentralized commit protocols that need O(kNN/sup 1/k/) messages and use k rounds of message interchanges is proposed. If k=ln N, then a decentralized commit protocol that needs O(Nln N) messages only is obtained. The communication scheme is also used to derive some decentralized consensus protocols.>