article

Free access

Quorum consensus in nested-transaction systems

Editor: Won Kim Authors:

Kenneth J. Goldman,

Nancy LynchAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 19, Issue 4

Pages 537 - 585

https://doi.org/10.1145/195664.195666

Published: 01 December 1994 Publication History

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.

References

[1]

ASPNES, J., FEKETE, A, LYNCH, N, MERRITT, M., AND WE{HL, W. 1988. A theory of t~mestampbased concurrency control for nested transactions. In Proceedings of the 14th International Conference on Ve~T Large Data Bases VLDB Endowment, 431 444.

[2]

BARBARA, D, AND GARCIA-MOLINA, H. 1985. Mutual exclusmn m part, tinned distributed sys-tems. Tech. Rep. TR-346, Dept. Computer Science, Princeton Umv., Princeton, N.J

[3]

BERNSTEIN, P., HADZILACOS, V., AND GOODMAN, N. 1987 Concurrency Control and RecoveO' zn Database Systems Addison-Wesley, Reading, Mass.

[4]

EAGER, D., AND SEVCIK, K. 1983 Robustness in distributed database systems. ACM Trans. Database Syst 8, 3 (Sept.) 354 381.

[5]

EL ABADm, A, TOUE% S. 1989. Maintaining avmlabihty in partitioned replicated databases. ACM Trans Database Syst. 14, 2 tJune) 264-290.

[6]

EL ABRAm, A., SKEEN, D., AND CmsTIaN, F. 1985 An efficmnt fault-tolerant protocol for replicated data management In ProceedLngs of the 4th ACM Symposium on Principles of Database Systems (Portland, Oregon, Mar.). ACM, New York, 215-229

[7]

FEKET~, A, LYNCH, N., MERRITT, M., AND WEIHL, W. 1990 Commutatiwty-based locking for nested transactmns. J Comput. Syst Scz. (Aug.) 65 156.

[8]

FEKETE, A., LYNCH, N., MERR{TT, M., AND WEIHL, W. 1987. Nested transactmns and read/write locking. In Proceedings of the 6th ACM Symposium on Pnnc~ples o{ Database Systems (San Diego, CA, Mar.). ACM, New York, 97 111 Expanded version available as Tech. Memo MIT/LCS/TM-324, Laboratory for Computer Science, MIT, Cambridge, Mass, April

[9]

GiFFORD, D 1979. Weighted voting for replicated data. In Proceedings of the 7th ACM Symposium on Operatlng Systera Prmctples. ACM, New York, 150 162.

[10]

HERMHY, M. 1987. Extending multlversion time-stamping protocols to exploit type informatmn IEEE Trans Compat C-36, 4 (Apr.).

[11]

HERLIHY, M. 1984. Rephcatmn methods for abstract data types. Tech. Rep. MIT/LCS/TR-319, MIT Laboratory for Computer Science, Cambridge, Mass, May.

[12]

HERLIHY, M., LYNCH, N., MEm~ITT, M, ANn WEmL, W. 1987. On the correctness of orphan elimination algorithms In Proceedings of the 17th IEEE Symposium on Fault-Tolerant Computzn~ IEEE, Now York, g 13 Also, MIT/LCS/TM 829, MIT Laboratory for computer Science, Cambridge, Mass., May. To appear in J. ACM.

[13]

JAJODIA, S., AND MUTCHLER, D. 1990 Dynamic voting algorithms for maintaining the consistency of rep}icated databases ACM Trans. Database Syst. 15 (June), 230-280.

[14]

LYNCH, N, AND MERRITT, M. 1986. Introductmn to the theory of nested transactions. Theoret. Comput. Scz. 62, 123-185. Also in International Conference on Database Theory (Rome, Italy, Sept.) 278-305. Expanded version m MIT/LCS/TR-367 July.

[15]

LYNCH, N, AND TUTTI,E, M. 1987. Hierarchical correctness proofs for distributed algorithms. In Proceedings of 6th ACM Symposium on Principles of Dzstrzbuted Computatwn. ACM, New York, 137-151 Expanded vermon avmlab}e as Tech Rep. MIT/LCS/TR-387, Laboratory for Computer Scmnce, MIT Cambridge, Mass., Apr

[16]

MOSS~ J. E. B. 1981. Nested transactions: An approach to reliable distributed computing. Ph.D. thesis, MIT, Cambridge, Mass. Tech. Rep. MIT/LCS/TR-260, Laboratory for Computer Science, MIT, Apr. Also, published by MIT Press, Mar. 1985.

[17]

REED, D. 1983. Implementing atomic actions on decentralized data. 1983. ACM Tra~zs. Comput. Syst. 1, i (Feb.) 3 23.

[18]

THOMAS, R. 1979. A majority consensus approach to concurrency control for multiple copy databases. ACM Trans. Database Syst. 4, 2 (June) 180-209.

Cited By

MADRIA SMAHESHWARI SCHANDRA BBHARGAVA B(2012)FORMALIZATION AND PROOF OF CORRECTNESS OF THE CRASH RECOVERY ALGORITHM FOR AN OPEN AND SAFE NESTED TRANSACTION MODELInternational Journal of Cooperative Information Systems10.1142/S021884300100024210:01n02(1-50)Online publication date: May-2012
https://doi.org/10.1142/S0218843001000242
Gilbert SLynch NShvartsman A(2010)RamboDistributed Computing10.1007/s00446-010-0117-123:4(225-272)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1007/s00446-010-0117-1
Armendáriz-Iñigo JGonzález de Mendívil JGaritagoitia JMuñoz-Escoí F(2009)Correctness proof of a database replication protocol under the perspective of the I/O automaton modelActa Informatica10.1007/s00236-009-0097-446:4(297-330)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1007/s00236-009-0097-4
Show More Cited By

Index Terms

Quorum consensus in nested-transaction systems

Recommendations

Consensus on transaction commit

The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms also reach agreement, but ...
Generalized Grid Quorum Consensus for Replica Control Protocol
CICN '11: Proceedings of the 2011 International Conference on Computational Intelligence and Communication Networks

In distributed systems it is often necessary to provide coordination among the multiple concurrent processes to tolerate the contention, periods of asynchrony and a number of failures. Quorum systems provide a decentralized approach for such ...
Speculation Based Nested Locking Protocol to Increase the Concurrency of Nested Transactions
IDEAS '00: Proceedings of the 2000 International Symposium on Database Engineering & Applications

The authors propose an improved concurrency control protocol based on speculation for nested transactions and explain how it increases both intraand inter-transaction concurrency as compared to J.E.B. Moss's (1985) nested locking protocol. In the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 19, Issue 4

Dec. 1994

126 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/195664

Editor:
Won Kim
UniSQL Inc., Austin, TX

Issue’s Table of Contents

Copyright © 1994 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1994

Published in TODS Volume 19, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
569
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)24

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

MADRIA SMAHESHWARI SCHANDRA BBHARGAVA B(2012)FORMALIZATION AND PROOF OF CORRECTNESS OF THE CRASH RECOVERY ALGORITHM FOR AN OPEN AND SAFE NESTED TRANSACTION MODELInternational Journal of Cooperative Information Systems10.1142/S021884300100024210:01n02(1-50)Online publication date: May-2012
Gilbert SLynch NShvartsman A(2010)RamboDistributed Computing10.1007/s00446-010-0117-123:4(225-272)Online publication date: 1-Dec-2010
Armendáriz-Iñigo JGonzález de Mendívil JGaritagoitia JMuñoz-Escoí F(2009)Correctness proof of a database replication protocol under the perspective of the I/O automaton modelActa Informatica10.1007/s00236-009-0097-446:4(297-330)Online publication date: 19-Jun-2009
Guerraoui ROliveira RSchiper A(2005)Atomic updates of replicated dataDependable Computing — EDCC-210.1007/3-540-61772-8_49(365-381)Online publication date: 6-Jun-2005
Madria SMaheshwari SChandra B(2001)Formalization and correctness of a concurrent linear hash structure algorithm using nested transactions and I/O automataData & Knowledge Engineering10.1016/S0169-023X(01)00005-237:2(139-176)Online publication date: 1-May-2001
Madria SMaheshwari SChandra B(2001)Virtual partition algorithm in a nested transaction environment and its correctnessInformation Sciences: an International Journal10.1016/S0020-0255(01)00111-6137:1-4(211-244)Online publication date: 1-Sep-2001
Madria SMaheshwari SChandra B(2001)On the Correctness of Virtual Partition Algorithm in a Nested Transaction EnvironmentAdvances in Databases and Information Systems10.1007/3-540-48252-0_8(98-112)Online publication date: 29-Mar-2001
Kshemkalyani ASinghal M(1999)A One-Phase Algorithm to Detect Distributed Deadlocks in Replicated DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/69.82460111:6(880-895)Online publication date: 1-Nov-1999
(1996)BibliographyDistributed Algorithms10.1016/B978-1-55860-348-6.50026-2(829-856)Online publication date: 1996
Lynch N(1996)Distributed AlgorithmsundefinedOnline publication date: 16-Apr-1996

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents