article

Open access

Local atomicity properties: modular concurrency control for abstract data types

Editor: Susan L. Graham Author:

W. E. WeihlAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 11, Issue 2

Pages 249 - 282

https://doi.org/10.1145/63264.63518

Published: 01 April 1989 Publication History

PDF eReader

Abstract

Atomic actions (or transactions) are useful for coping with concurrency and failures. One way of ensuring atomicity of actions is to implement applications in terms of atomic data types: abstract data types whose objects ensure serializability and recoverability of actions using them. Many atomic types can be implemented to provide high levels of concurrency by taking advantage of algebraic properties of the type's operations, for example, that certain operations commute. In this paper we analyze the level of concurrency permitted by an atomic type. We introduce several local constraints on individual objects that suffice to ensure global atomicity of actions; we call these constraints local atomicity properties. We present three local atomicity properties, each of which is optimal: no strictly weaker local constraint on objects suffices to ensure global atomicity for actions. Thus, the local atomicity properties define precise limits on the amount of concurrency that can be permitted by an atomic type.

References

[1]

ALLCHIN, J. E., AND MCKENDRY, M.S. Synchronization and recovery of actions. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Aug. 17- 19, 1983). ACM, New York, 1983, pp. 31-44.

Crossref

Google Scholar

[2]

ASPNES, J., FEKETE, A., LYNCH, N., MERRITT, M., AND WEIHL, W. A theory of timestampbased concurrency control for nested transactions. In Proceedings of the Symposium on Very Large Databases (Los Angeles, Aug. 29-Sept. 1, 1988). 1EEE, New York, 1988, pp. 431-444.

Crossref

Google Scholar

[3]

BEERI, C., ET AL. A concurrency control theory for nested transactions. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Aug. 17-19, 1983). ACM, New York, 1983, pp. 45-62.

Crossref

Google Scholar

[4]

BERNSTEIN, P. A., AND GOODMAN, N. Concurrency control in distributed database systems. ACMComput. Surv. I3, 2 (June 1981), 185-221.

Crossref

Google Scholar

[5]

BERNSTEIN, P. A., AND GOODMAN, N. Multiversion concurrency control--Theory and algorithms. ACM Trans. Database Syst. 8, 4 (Dec. 1983), 465-483.

Crossref

Google Scholar

[6]

BERNSTEIN, P., GOODMAN, N., AND LAI, M.-Y. Analyzing concurrency control when user and system operations differ. IEEE Trans. Softw. Eng. SE-9, 3 (May 1983), 223-239.

Google Scholar

[7]

CAREY, M. J., AND MUHANNA, W. A. The performance of multi-version concurrency control algorithms. Tech. Rep. 550, Computer Science Dept., Univ. of Wisconsin at Madison, Aug. 1984.

Google Scholar

[8]

CHAN, A., AND GRAY, R. Implementing distributed read-only transactions. IEEE Trans. Softw. Eng. SE-11, 2 (Feb. 1985), 205-212.

Google Scholar

[9]

DAVIES, C.T. Recovery semantics for a DB/DC system. In Proceedings of the ACM Annual Conference (Atlanta, Ga., Aug. 27-29, 1973). ACM, New York, 1973, pp. 136-141.

Crossref

Google Scholar

[10]

DAVIES, C.T. Data processing spheres of control. IBM Syst. J. 17, 2 (1978), 179-198.

Google Scholar

[11]

DuBOURDIEU, D. J. Implementation of distributed transactions. In Proceedings of the 6th Berkeley Workshop on Distributed Data Management and Computer Networks. (Berkeley, Calif., Feb. 16-19, 1982). Lawrence Berkeley Lab., Univ. of California, Berkeley, 1982, pp. 81-94.

Google Scholar

[12]

ESWARAN, K. P., GRAY, J. N., LORIE, R. a., AND TRAIGER, I.r. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624-633.

Crossref

Google Scholar

[13]

FEKETE, A., LYNCH, N., MERRIT, M., AND WEIHL, W. Commutativity-based locking for nested transactions. Tech. Rep. MIT-LCS TM-370, Dept. of Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1988.

Google Scholar

[14]

GRAY, J. Notes on database operating systems. In Operating Systems--An Advanced Course. Lecture Notes in Computer Science, vol. 60. Springer-Verlag, New York, 1978, pp. 393-481.

Crossref

Google Scholar

[15]

HADZlLACOS, V. A theory of reliability in database systems. J. ACM 35, i (Jan. 1988), 121-145.

Crossref

Google Scholar

[16]

HERL1HY, M.P. Comparing how atomicity mechanisms support replication. In Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing (Minaki, Canada, Aug. 5-7, 1985). ACM, New York, 1985, pp. 102-110.

Crossref

Google Scholar

[17]

HERLIHY, M.P. Optimistic concurrency control for abstract data types. In Fifth ACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing (Aug. 11-13, 1986). ACM, New York, 1986, pp. 206-217.

Crossref

Google Scholar

[18]

HERLIHY, M.P. Extending multiversion timestamping protocols to exploit type information. Special issue on parallel and distributed computing. IEEE Trans. Comput. C-36, 4 (Apr. 1987).

Crossref

Google Scholar

[19]

HERLIHY, M., AND WEIHL, W. Hybrid concurrency control for abstract data types. In Proceedings of the ACM Symposium on Principles of Database Systems (Austin, Tex., Mar. 21-23, 1988). ACM, New York, 1988, pp. 201-210.

Crossref

Google Scholar

[20]

HERLIHY, M. P., LYNCH, N., MERRITT, m., AND WE1HL, W. On the correctness of orphan elimination algorithms, d. ACM. To be published. (Also available as MIT/LCS/TM-329. A preliminary version was published in the Seventeenth International Symposium on Fault-Tolerant Computing in 1987.)

Google Scholar

[21]

KORTH, H.F. Locking protocols: General lock classes and deadlock freedom. Ph.D. thesis, Dept. of Computer Science, Princeton Univ., Princeton, N.J., 1981.

Crossref

Google Scholar

[22]

KUNG, H. T., AND PAPAD{MITR1OU, C. H. An optimality theory of concurrency control for databases. Acta Inf. 19, 1 (Apr. 1983), 1-11.

Google Scholar

[23]

KUNG, H. T., AND ROBINSON, J. T. On optimistic methods for concurrency control. ACM Trans. Database Syst. 6, 2 (June 1981), 213-226.

Crossref

Google Scholar

[24]

LAMPORT, L. Time, clocks and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.

Crossref

Google Scholar

[25]

LAMPSON, B. Atomic transactions. In Distributed Systems: Architecture and Implementation, Lecture Notes in Computer Science, vol. 105, E. Goos and J. Hartmanis, Eds. Springer-Verlag, Berlin, 1981, pp. 246-265.

Crossref

Google Scholar

[26]

LISKOV, B., AND SCHE{FLER, R. Guardians and actions: Linguistic support for robust, distributed programs. ACM Trans. Program. Lang. Syst. 5, 3 (July 1983), 381-404.

Crossref

Google Scholar

[27]

LISKOV, B., AND WEIHL, W. Specifications of distributed programs. Distrib. Comput. I, 2 (1986), 102-118.

Google Scholar

[28]

LISKOV, B., AND ZILLES, S.N. Programming with abstract data types. In Proceedings of the ACM-SIGPLAN Conference on Very High Level Languages. ACM SIGPLAN Not. 9, 4 (Apr. 1974), 50-59.

Crossref

Google Scholar

[29]

LISKOV, B., SCHE{FLER, R., WALKER, E. F., AND WEIHL, W. Orphan detection (extended abstract). In Proceedings of the 17th International Symposium on Fault-Tolerant Computing (Pittsburgh, Pa., July 6-8, 1987). IEEE, New York, 1987, pp. 2-7.

Google Scholar

[30]

LYNCH, N.A. Concurrency control for resilient nested transactions. In Proceedings of the 2nd ACM Symposium on Principles of Database Systems (Atlanta, Ga., Mar. 21-23, 1983). ACM, New York, 1983, pp. 166-181. (Revised version to appear in Adv. Comput. Res.)

Crossref

Google Scholar

[31]

LYNCH, N. A., MERRITT, U., WEIHL, W., AND FEKETE, A. A theory of atomic transactions. Tech. Rep. MIT-LCS-TM-362, Dept. of Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1988. (Also appeared in the Proceedings of the 1988 International Conference on Database Theory.)

Crossref

Google Scholar

[32]

Moss, J. E. B. Nested transactions: An approach to reliable distributed computing. Ph.D. thesis, Dept. of Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1981. (Also available as Tech. Rep. MIT/LCS/TR*260.)

Crossref

Google Scholar

[33]

PAPADIMITRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct. 1979), 631-653.

Crossref

Google Scholar

[34]

PAPADIMITRIOU, C. H., AND KANELLAKIS, P. On concurrency control by multiple versions. ACM Trans. Database Syst. 9, i (Mar. 1984), 89-99.

Crossref

Google Scholar

[35]

Pu, C. Superdatabases for composition of heterogeneous databases. In Proceedings of the 4th Data Engineering Conference (Los Angeles, Calif., Feb. 1-5, 1988). IEEE, New York, 1988, pp. 548-555. (Also available as Tech. Rep. CUCS-243-86, Columbia Univ., Dept. of Computer Science).

Crossref

Google Scholar

[36]

REED, D.P. Naming and synchronization in a decentralized computer system. Ph.D. thesis, Dept. of Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1978. (Also available as Tech. Rep. MIT/LCS/TR-205.)

Crossref

Google Scholar

[37]

SCHWARZ, P., AND SPECTOR, A. Synchronizing shared abstract types. ACM Trans. Comput. Syst. 2, 3 (Aug. 1984), 223-250.

Crossref

Google Scholar

[38]

SILBERSCHATZ, A., AND KEDEM, Z. Consistency in hierarchical database systems. J. ACM 27, I (Jan. 1980), 72-80.

Crossref

Google Scholar

[39]

SILBERSCHATZ, A., AND KEDEM, Z. A family of locking protocols for database systems that are modeled by directed graphs. IEEE Trans. Softw. Eng. 8, 6 (Nov. 1982), 558-562.

Google Scholar

[40]

SKEEN, M.D. Crash recovery in a distributed database system. Ph.D. thesis, Dept. of Computer Science, Univ. of California at Berkeley, May 1982. (Also available as UCB/ERL M82/45.)

Google Scholar

[41]

WEIHL, W.r. Data-dependent concurrency control and recovery. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Aug. 17-19, 1983). ACM, New York, 1983, pp. 63-75.

Crossref

Google Scholar

[42]

WEIHL, W.E. Specification and implementation of atomic data types. Ph.D. thesis, Dept. of Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1984. (Also available as Tech. Rep. MIT/LCS/TR-314.)

Crossref

Google Scholar

[43]

WEIHL, W.E. Distributed version management for read-only actions. IEEE Trans. Softw. Eng. SE-13, 1 (Jan. 1987), 55-64.

Crossref

Google Scholar

[44]

WEIHL, W.r. Commutativity-based concurrency control for abstract data types. IEEE Trans. Comput. 37, 12 (Dec. 1988), 1488-1505. (Also available as Tech. Rep. MIT/LCS/TM-367.)

Crossref

Google Scholar

[45]

WEIHL, W. r. The impact of recovery on concurrency control. In Proceedings of the ACM Symposium on Principles of Database Systems (Philadelphia, Pa., Mar. 29-31, 1989). ACM, New York, 1989.

Crossref

Google Scholar

[46]

WEIHL, W., AND LISKOV, B. Implementation of resilient, atomic data types. ACM Trans. Program. Lang. Syst. 17, 2 (Apr. 1985), 244-269.

Crossref

Google Scholar

Cited By

View all

Siek KWojciechowski P(2022)Last-use opacity: a strong safety property for transactional memory with prerelease supportDistributed Computing10.1007/s00446-022-00420-235:3(265-301)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s00446-022-00420-2
Ranjan NShang ZKrishnan SElmore A(2021)Version Reconciliation for Collaborative DatabasesProceedings of the ACM Symposium on Cloud Computing10.1145/3472883.3486980(473-488)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3472883.3486980
(2021)BibliographyThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00033-1(533-540)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00033-1
Show More Cited By

Recommendations

Adaptable concurrency control for atomic data types

In many distributed systems concurrent access is required to a shared object, where abstract object servers may incorporate type-specific properties to define consistency requirements. Each operation and its outcome is treated as an event, and conflicts ...
Commutativity-Based Concurrency Control for Abstract Data Types

Two novel concurrency algorithms for abstract data types are presented that ensure serializability of transactions. It is proved that both algorithms ensure a local atomicity property called dynamic atomicity. The algorithms are quite general, ...
Hybrid concurrency control for abstract data types
PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

We define a new locking protocol that permits more concurrency than existing commutativity-based protocols. The protocol uses timestamps generated when transactions commit to provide more information about the serialization order of transactions, and ...

Reviews

Reviewer: Arno Schmitt

This paper deals with the problem of preserving consistency of data in the presence of concurrency and failure. To this end the author introduces atomic transactions, which guarantee serializability and recoverability. Serializability means that the concurrent execution of atomic transactions is equivalent to some serial execution, and recoverability means that failing actions have no effect on the data. Therefore, in order to prove that a (concurrent) system preserves consistency of data it is sufficient to prove that each serial execution preserves consistency. In Section 2 the author introduces systems composed of transactions and objects. Each component of such a system owns a behavioral specification. This specification describes how the component constrains the occurrence of events in which it participates. The specifications are represented by sets of histories. Moreover, the specification of an object consists of a serial part, which describes the object's behavior in the absence of concurrency and failure. The serial specification of an object is given by a state machine. In the next section, atomic histories are defined. Informally, an atomic history is a history in which the committed transactions can be executed in some serial order and have the same effect. (A committed transaction is a transaction that terminates successfully.) The last section presents the main results: three “local atomicity properties” of specifications of objects. For each such property P the following theorems are proved. (1)If every object in a system satisfies the property P, then every history in the system's behavior is atomic. (2)Property P is optimal, that is, no strictly weaker property Q exists that makes Theorem 1 true. These local atomicity properties are generalizations of several known protocols. The author briefly discusses the connections between the local atomicity properties and these protocols. The paper is well written in a precise mathematical style and contains a lot of short examples. It is interesting for people working in the theory and practice of database management and concurrent systems.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 11, Issue 2

April 1989

176 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/63264

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1989

Published in TOPLAS Volume 11, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

130
Total Citations
View Citations
721
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)9

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Siek KWojciechowski P(2022)Last-use opacity: a strong safety property for transactional memory with prerelease supportDistributed Computing10.1007/s00446-022-00420-235:3(265-301)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s00446-022-00420-2
Ranjan NShang ZKrishnan SElmore A(2021)Version Reconciliation for Collaborative DatabasesProceedings of the ACM Symposium on Cloud Computing10.1145/3472883.3486980(473-488)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3472883.3486980
(2021)BibliographyThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00033-1(533-540)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00033-1
Herlihy MShavit NLuchangco VSpear M(2021)Concurrent objectsThe Art of Multiprocessor Programming10.1016/B978-0-12-415950-1.00012-4(49-74)Online publication date: 2021
https://doi.org/10.1016/B978-0-12-415950-1.00012-4
Li ZLiu LDeng YWang JLiu ZYin SWei S(2019)FPGA-Accelerated Optimistic Concurrency Control for Transactional MemoryProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358270(911-923)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358270
Huang SXu LLiu JElmore AParameswaran A(2017)OrpheusDBProceedings of the VLDB Endowment10.14778/3115404.311541710:10(1130-1141)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.14778/3115404.3115417
Li YKatsipoulakis NChandramouli BGoldstein JKossmann D(2017)MisonProceedings of the VLDB Endowment10.14778/3115404.311541610:10(1118-1129)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.14778/3115404.3115416
Zhang FZhang YQin LZhang WLin X(2017)When engagement meets similarityProceedings of the VLDB Endowment10.14778/3115404.311540610:10(998-1009)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.14778/3115404.3115406
Su CCrooks NDing CAlvisi LXie CChirkova RYang JSuciu D(2017)Bringing Modular Concurrency Control to the Next LevelProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3064031(283-297)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3064031
(2017)BibliographyDistributed Systems10.1016/B978-1-78548-226-7.50013-6(149-156)Online publication date: 2017
https://doi.org/10.1016/B978-1-78548-226-7.50013-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Adaptable concurrency control for atomic data types

Commutativity-Based Concurrency Control for Abstract Data Types

Hybrid concurrency control for abstract data types

Reviews

Access critical reviews of Computing literature here