More Web Proxy on the site http://driver.im/

Article

Free access

The impact of recovery on concurrency control

Author:

W. E. WeihlAuthors Info & Claims

PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 259 - 269

https://doi.org/10.1145/73721.73748

Published: 29 March 1989 Publication History

Abstract

It is widely recognized by practitioners that concurrency control and recovery for transaction systems interact in subtle ways. In most theoretical work, however, concurrency control and recovery are treated as separate, largely independent problems. In this paper we investigate the interactions between concurrency control and recovery. We consider two general recovery methods for abstract data types, update-in-place and deferred-update. While each requires operations to conflict if they do not “commute,” the two recovery methods require subtly different notions of commutativity. We give a precise characterization of the conflict relations that work with each recovery method, and show that each permits conflict relations that the other does not. Thus, the two recovery methods place incomparable constraints on concurrency control. Our analysis applies to arbitrary abstract data types, including those with operations that may be partial or non-deterministic.

References

[1]

Allchin, J. E. An architecture for reliable decentralized= systems. Ph.D. Tit., Georgia Institute of Technology, September 1983. Available as Technical Report G!T-ICS-83/23.

Digital Library

[2]

Beeri, C., et al, A concurrency control theory for nested transactions. Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, ACM, Montreal, Canada, August, 1983, pp. 45-62.

Digital Library

[3]

Bemstein, P. A., and Goodman, N. "Concurrency control in distributed database systems". ACM Computing Surveys 13, 2 (June 1981), 185-221.

Digital Library

[4]

Bemstein, P., Goodman, N., and Lai, M.-Y. "Analyzing concurrency control when user and system operations differ". IEEE Transactions on Software Engineering SE-9, 3 (May 1983), 223-239.

[5]

Eswaran, K. P., Gray, J. N., Lode, R. A., and Traiger, I. L. "/'he notions of consistency andpredicate locks in a database system". Comm. ACM 19, 11 (November 1976), 624-633.

Digital Library

[6]

Gray, L Lecture Notes in Computer Science. Volume 60: Notes on Database Ot~ating Systems. In Operating Systems -- An Advanced Course, Springer-Verlag, 1978.

Digital Library

[7]

Gray, J.N., et al. "The recovery manager of the System R database manager". ACM Computing Surveys 13, 2 (June 1981 ), 223-242.

Digital Library

[8]

Hadzilacos, V. "A theory of reliability in database systems". Journal of the ACM 35, 1 (January 1988), 121-145.

Digital Library

[9]

Korth, H. F. "Locking Primitives in a Database System". Journal of the Association for Computing Machinery 30, 1 (January 1983), 55-79.

Digital Library

[10]

Kung, H.T., and Robinson, J.T. "On optimistic methods for concurrency control". ACM Transactions on Database Systems 6, 2 (June 1981), 213-226.

Digital Library

[11]

I.,ampson, B. Lecture Notes in Computer Science. Volume 105: Atomic transactions. In DistributedSystems: Architecture and Implementation, Goos and Hartmanis, Eds., Springer-Vedag, Berlin, 1981, pp. 246-265.

Digital Library

[12]

Liskov, B., and Scheifler, R. "Guardians and actions: linguistic support for robust, distributed programs". ACM Trans. actions on Programming Languages and Systems 5, 3 (July 1983), 381-404.

Digital Library

[13]

Lynch, N. A., and M. R. Turtle. Hierarchical corr~mess proofs for distributed algorithms. Tech. Rept. Mrr/I~S/TR-387, MIT Laboratory for Computer Science, April, 1987.

Digital Library

[14]

Mitc~~ll, J. G. and Dion, J, "A comparison of two networkbased file servers". Communications of the ACM 25,4 (April 1982), 233-245. Special issue: Selected papers from the Eighth Symposium on Operating Systems Principles.

Digital Library

[15]

Moss, J., N. Griffeth, M. Graham. Abstraction in concurrency control and recovery management (revised). Tech. Rept. COINS Technical Reptm 86-20, University of Massachusetts at Amherst, May, 1986.

Digital Library

[16]

O'Neil, P. E. "The escrow transactional meth~". ACM Transactions on Database Systems 11, 4 (December 1986), 405-430.

Digital Library

[17]

Papadimitriou, C.H. "The serializability of concturent database updates'. Journal of theACM 26, 4 (October 1979), 631-653.

Digital Library

[18]

Schwarz, P. M., and Spector, A.Z. "Synchronizing shared abstract types'. ACM Transactions on Conjurer Systems 2, 3 (August 1984), 223-250.

Digital Library

[19]

Skeen, M. D. Crash recovery in a distributed database system. Ph.D. Th., University of California at Berkeley, May 1982. Available as UCB/ERL M82/45.

[20]

Spector, A. Z., et aL "Suptx~ for distributed trensactions in the TABS prototype". IEEE Transactions on $oj~are Engineering SE-II, 6 (June 1985), 520-530.

Digital Library

[21]

W.E. Weihl. Specification and implementation of atomic data types. Ph.D. Th., MIT, 1984. Available as Technical Report M1T/LCS/TR-314.

Digital Library

[22]

W.E. Weild, "Commutativity-based Concurrency Control for Abstract Data Types". IEEE Transactions on Computers 37, 12 (December 1988), 1488-1505. Also available as MrF/L~S/TM-367.

Digital Library

[23]

W.E. Weibl. "Local atomicity properties: modular concurrency control for abstract data types". ACM Transactions on Programming Languages and Systems 11 (1989). Accepted for publication.

Digital Library

[24]

Weikum, G. A theoretical foundation of multi-level concurrency control. Proceedings of the Fifth ACM Symposium on Principles of Database Systems, 1986, pp. 31-42.

Digital Library

[25]

Weikum, G., and H.-J. Schek. Architectural issues of transaction management in multi-layered systems. Proceedings of the Tenth International Conference on Very Large Data Bases, Singapore, August, 1984, pp. 454-465.

Digital Library

Cited By

Eberhard JTripathi A(2010)Semantics-Based Object Caching in Distributed SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.4821:12(1750-1764)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/TPDS.2010.48
Wu DWong M(2010)A Synchronization Approach for Increasing Concurrency in Software Transactional MemoryProceedings of the 2010 Ninth International Conference on Grid and Cloud Computing10.1109/GCC.2010.46(185-190)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/GCC.2010.46
Eberhard JTripathi A(2005)Object-Based Commutativity Analysis for Real-Time ApplicationsProceedings of the 10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems10.1109/WORDS.2005.44(279-286)Online publication date: 2-Feb-2005
https://dl.acm.org/doi/10.1109/WORDS.2005.44
Show More Cited By

Index Terms

The impact of recovery on concurrency control

Recommendations

Semantics-based concurrency control: beyond commutativity

The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enchanced concurrency ...
Rethinking serializable multiversion concurrency control

Multi-versioned database systems have the potential to significantly increase the amount of concurrency in transaction processing because they can avoid read-write conflicts. Unfortunately, the increase in concurrency usually comes at the cost of ...
Semantic recovery and concurrency control for object bases

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

March 1989

401 pages

ISBN:0897913086

DOI:10.1145/73721

Chairman:
Avi Silberschatz
Univ. of Texas, Austin

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODS '89

Sponsor:

PODS '89: Principles of database systems

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
427
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Eberhard JTripathi A(2010)Semantics-Based Object Caching in Distributed SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.4821:12(1750-1764)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/TPDS.2010.48
Wu DWong M(2010)A Synchronization Approach for Increasing Concurrency in Software Transactional MemoryProceedings of the 2010 Ninth International Conference on Grid and Cloud Computing10.1109/GCC.2010.46(185-190)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/GCC.2010.46
Eberhard JTripathi A(2005)Object-Based Commutativity Analysis for Real-Time ApplicationsProceedings of the 10th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems10.1109/WORDS.2005.44(279-286)Online publication date: 2-Feb-2005
https://dl.acm.org/doi/10.1109/WORDS.2005.44
Leong HAgrawal DAgre J(2005)Using message semantics to reduce rollback in the time warp mechanismDistributed Algorithms10.1007/3-540-57271-6_44(309-323)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57271-6_44
Mak HWong M(2000)An experimental study of semantics-based concurrency control protocolsData & Knowledge Engineering10.1016/S0169-023X(00)00022-735:1(53-81)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1016/S0169-023X%2800%2900022-7
Jun W(2000)A multi-granularity locking-based concurrency control in object-oriented database systemsJournal of Systems and Software10.1016/S0164-1212(00)00038-854:3(201-217)Online publication date: 1-Nov-2000
https://dl.acm.org/doi/10.1016/S0164-1212%2800%2900038-8
Muth P(1997)Application Specific Transaction Management in MultidatabaseSystemsDistributed and Parallel Databases10.1023/A:10086365279425:4(357-403)Online publication date: 1-Oct-1997
https://dl.acm.org/doi/10.1023/A%3A1008636527942
Wong MAgrawal DMak H(1997)Bounded Inconsistency for Type-Specific Concurrency ControlDistributed and Parallel Databases10.1023/A:10086229219175:1(31-75)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.1023/A%3A1008622921917
Agrawal DChoy MVa Leong HSingh AAnderson JPeleg DBorowsky E(1994)Mixed consistencyProceedings of the thirteenth annual ACM symposium on Principles of distributed computing10.1145/197917.197967(101-110)Online publication date: 14-Aug-1994
https://dl.acm.org/doi/10.1145/197917.197967
Pal SLanka S(1994)Isolation of transaction aborts in object-oriented database systemsProceedings of the third international conference on Information and knowledge management10.1145/191246.191275(179-186)Online publication date: 29-Nov-1994
https://dl.acm.org/doi/10.1145/191246.191275
Show More Cited By

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 Publication

Media

Figures

Other

Tables

View Table of Contents