Open Commit Protocols Tolerating Commission Failures.

@article{DBLP:journals/tods/RothermelP93,
  author    = {Kurt Rothermel and
               Stefan Pappe},
  title     = {Open Commit Protocols Tolerating Commission Failures},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {2},
  year      = {1993},
  pages     = {289-332},
  ee        = {http://doi.acm.org/10.1145/151634.151638, db/journals/tods/RothermelP93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

To ensure atomicity of transactions in distributed systems so-called 2-phase commit (2PC) protocols have been proposed. The basic assumption of these protocols is that the processing nodes involved in transactions are "sane," i.e., they only fail with omission failures, and nodes eventually recover from failures. Unfortunately, this assumption is not realistic for so-called Open Distributed Systems (ODSs), in which nodes may have totally different reliability characteristics. In ODSs, nodes can be classified into trusted nodes (e.g., a banking server) and nontrusted nodes (e.g., a home PC requesting a remote banking service). While trusted nodes are assumed to be sane, nontrusted nodes may fail permanently and even cause commission failures to occur.

In this paper, we propose a family of 2PC protocols that tolerate any number of omission failures at trusted nodes and any number of commission and omission failures at nontrusted nodes. The proposed protocols ensure that (at least) the trusted nodes participating in a transaction eventually terminate the transaction in a consistent manner. Unlike Byzantine commit protocols, our protocols do not incorporate mechanisms for achieving Byzantine agreement, which has advantages in terms of complexity: Our protocols have the same or only a slightly higher message complexity than traditional 2PC protocols.

Copyright © 1993 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[1]

Arvola Chan, Umeshwar Dayal, Stephen Fox, Nathan Goodman, Daniel R. Ries, Dale Skeen: Overview of an Ada Compatible Distributed Database Manager. SIGMOD Conference 1983: 228-237 BibTeX

[2]

...

[3]

...

[4]

...

[5]

...

[6]

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

[7]

Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983) BibTeX

[8]

Roger L. Haskin, Yoni Malachi, Wayne Sawdon, Gregory Chan: Recovery Management in QuickSilver. ACM Trans. Comput. Syst. 6(1): 82-108(1988) BibTeX

[9]

...

[10]

...

[11]

...

[12]

Butler W. Lampson: Atomic Transactions. Advanced Course: Distributed Systems 1980: 246-265 BibTeX

[13]

Leslie Lamport, Robert E. Shostak, Marshall C. Pease: The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4(3): 382-401(1982) BibTeX

[14]

...

[15]

Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms, Robert A. Yost: Computation and Communication in R*: A Distributed Database Manager. ACM Trans. Comput. Syst. 2(1): 24-38(1984) BibTeX

[16]

C. Mohan, Bruce G. Lindsay: Efficient Commit Protocols for the Tree of Processes Model of Distributed Transactions. PODC 1983: 76-88 BibTeX

[17]

C. Mohan, Bruce G. Lindsay, Ron Obermarck: Transaction Management in the R* Distributed Database Management System. ACM Trans. Database Syst. 11(4): 378-396(1986) BibTeX

[18]

C. Mohan, H. Raymond Strong, Sheldon J. Finkelstein: Method for Distributed Transaction Commit and recovery Using Byzantine Agreement Within Clusters of Processors. PODC 1983: 89-103 BibTeX

[19]

Roger M. Needham, Michael D. Schroeder: Using Encryption for Authentication in Large Networks of Computers. Commun. ACM 21(12): 993-999(1978) BibTeX

[20]

Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2): 120-126(1978) BibTeX

[21]

...

[22]

...

[23]

Richard D. Schlichting, Fred B. Schneider: Fail-Stop Processors: An Approach to Designing Fault-Tolerant Computing Systems. ACM Trans. Comput. Syst. 1(3): 222-238(1983) BibTeX

[24]

Dale Skeen, Michael Stonebraker: A Formal Model of Crash Recovery in a Distributed System. Berkeley Workshop 1981: 129-142 BibTeX

[25]

...

[26]

...

[27]

...

[28]

...

[29]

...

[30]

...

[31]

...

Referenced by

1. Yousef J. Al-Houmaily, Panos K. Chrysanthis, Steven P. Levitan: An Argument in Favour of Presumed Commit Protocol. ICDE 1997: 255-265