Quorum Consensus in Nested Transaction Systems.

Kenneth J. Goldman, Nancy A. Lynch: Quorum Consensus in Nested Transaction Systems. ACM Trans. Database Syst. 19(4): 537-585(1994)

@article{DBLP:journals/tods/GoldmanL94,
  author    = {Kenneth J. Goldman and
               Nancy A. Lynch},
  title     = {Quorum Consensus in Nested Transaction Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {19},
  number    = {4},
  year      = {1994},
  pages     = {537-585},
  ee        = {http://doi.acm.org/10.1145/195664.195666, db/journals/tods/GoldmanL94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Gifford's Quorum Consensus algorithm for data replication is studied in the context of nested transactions and transaction failures (aborts), and a fully developed reconfiguration strategy is presented. A formal description of the algorithm is presented using the Input/Output automaton model for nested-transaction systems due to Lynch and Merritt. In this description, the algorithm itself is described in terms of nested transactions. The formal description is used to construct a complete proof of correctness that uses standard assertional techniques, is based on a natural correctness condition, and takes advantage of modularity that arises from describing the algorithm as nested transactions. The proof is accomplished hierarchically, showing that a fully replicated reconfigurable system "simulates" an intermediate replicated system, and that the intermediate system simulates an unreplicated system. The presentation and proof treat issues of data replication entirely separately from issues of concurrency control and recovery.

Copyright © 1994 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

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ...

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

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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

BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 3368 KB]

References

[Aspnes et al. 1988]: James Aspnes, Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: A Theory of Timestamp-Based Concurrency Control for Nested Transactions. VLDB 1988: 431-444 BibTeX
[Barbará and Garcia-Molina 1985]: Daniel Barbará, Hector Garcia-Molina: Mutual Exclusion in Partitioned Distributed Systems. Distributed Computing 1(2): 119-132(1986) BibTeX
[Bernstein et al. 1987]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Eager and Sevcik 1983]: Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX
[El Abbadi and Toueg 1989]: Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989) BibTeX
[El Abbadi et al. 1985]: Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229 BibTeX
[Fekete et al. 1990]: Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: Commutativity-Based Locking for Nested Transactions. J. Comput. Syst. Sci. 41(1): 65-156(1990) BibTeX
[Fekete et al. 1987]: Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: Nested Transactions and Read/Write Locking. PODS 1987: 97-111 BibTeX
[Gifford 1979]: David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[Herlihy 1987]: Maurice Herlihy: Extending Multiversion Time-Stamping Protocols to Exploit Type Information. IEEE Trans. Computers 36(4): 443-448(1987) BibTeX
[Herlihy 1984]: ...
[Herlihy et al. 1987]: ...
[Jajodia and Mutchler 1990]: Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990) BibTeX
[Lynch and Merritt 1988]: Nancy A. Lynch, Michael Merritt: Introduction to the Theory of Nested Transactions. Theor. Comput. Sci. 62(1-2): 123-185(1988) BibTeX
[Lynch and Tuttle 1987]: Nancy A. Lynch, Mark R. Tuttle: Hierarchical Correctness Proofs for Distributed Algorithms. PODC 1987: 137-151 BibTeX
[Moss 1981]: ...
[Reed 1983]: David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) BibTeX
[Thomas 1979]: Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX

Referenced by

Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra: On the Correctnes of Virtual Partition Algorithm in a Nested Transaction Environment. ADBIS 1999: 98-112

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]