On the Complexity of Commit Protocols.

@inproceedings{DBLP:conf/pods/Ramarao85,
  author    = {K. V. S. Ramarao},
  title     = {On the Complexity of Commit Protocols},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {235-244},
  ee        = {http://doi.acm.org/10.1145/325405.325447, db/conf/pods/Ramarao85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

1. 2logn-loglogn-logloglogn-0(1) lower bound on the time for nonblocking commit protocols,
2. impossibility of simultaneously achieving the optimal time and message bounds for commit protocols, both blocking and nonblocking, and
3. certain trade-offs between time and messages.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

...

[2]

Cynthia Dwork, Dale Skeen: The Inherent Cost of Nonblocking Commitment. PODC 1983: 1-11 BibTeX

[3]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[4]

Dale Skeen, Michael Stonebraker: A Formal Model of Crash Recovery in a Distributed System. IEEE Trans. Software Eng. 9(3): 219-228(1983) BibTeX

[5]

Dale Skeen: Nonblocking Commit Protocols. SIGMOD Conference 1981: 133-142 BibTeX

Referenced by

1. Ouri Wolfson: A Comparative Analysis of Two-Phase-Commit Protocols. ICDT 1990: 291-304
2. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
3. Adrian Segall, Ouri Wolfson: Transaction Commitment at Minimal Communication Cost. PODS 1987: 112-118
4. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
   Contents