Class of optimal decentralized commit protocols.

Shyan-Ming Yuan*, Ashok K. Agrawala

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

The message complexity of decentralized commit protocols is studied. It is shown that O(kNN1/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 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.

Original languageEnglish
Title of host publicationProceedings - International Conference on Distributed Computing Systems
PublisherPubl by IEEE
Pages234-241
Number of pages8
ISBN (Print)081860865X
DOIs
StatePublished - 1 Dec 1988

Publication series

NameProceedings - International Conference on Distributed Computing Systems
Volume8

Fingerprint Dive into the research topics of 'Class of optimal decentralized commit protocols.'. Together they form a unique fingerprint.

  • Cite this

    Yuan, S-M., & Agrawala, A. K. (1988). Class of optimal decentralized commit protocols. In Proceedings - International Conference on Distributed Computing Systems (pp. 234-241). (Proceedings - International Conference on Distributed Computing Systems; Vol. 8). Publ by IEEE. https://doi.org/10.1109/DCS.1988.12522