[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article
Open access

Local atomicity properties: modular concurrency control for abstract data types

Published: 01 April 1989 Publication History

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.
[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.
[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.
[4]
BERNSTEIN, P. A., AND GOODMAN, N. Concurrency control in distributed database systems. ACMComput. Surv. I3, 2 (June 1981), 185-221.
[5]
BERNSTEIN, P. A., AND GOODMAN, N. Multiversion concurrency control--Theory and algorithms. ACM Trans. Database Syst. 8, 4 (Dec. 1983), 465-483.
[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.
[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.
[8]
CHAN, A., AND GRAY, R. Implementing distributed read-only transactions. IEEE Trans. Softw. Eng. SE-11, 2 (Feb. 1985), 205-212.
[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.
[10]
DAVIES, C.T. Data processing spheres of control. IBM Syst. J. 17, 2 (1978), 179-198.
[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.
[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.
[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.
[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.
[15]
HADZlLACOS, V. A theory of reliability in database systems. J. ACM 35, i (Jan. 1988), 121-145.
[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.
[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.
[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).
[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.
[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.)
[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.
[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.
[23]
KUNG, H. T., AND ROBINSON, J. T. On optimistic methods for concurrency control. ACM Trans. Database Syst. 6, 2 (June 1981), 213-226.
[24]
LAMPORT, L. Time, clocks and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.
[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.
[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.
[27]
LISKOV, B., AND WEIHL, W. Specifications of distributed programs. Distrib. Comput. I, 2 (1986), 102-118.
[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.
[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.
[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.)
[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.)
[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.)
[33]
PAPADIMITRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct. 1979), 631-653.
[34]
PAPADIMITRIOU, C. H., AND KANELLAKIS, P. On concurrency control by multiple versions. ACM Trans. Database Syst. 9, i (Mar. 1984), 89-99.
[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).
[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.)
[37]
SCHWARZ, P., AND SPECTOR, A. Synchronizing shared abstract types. ACM Trans. Comput. Syst. 2, 3 (Aug. 1984), 223-250.
[38]
SILBERSCHATZ, A., AND KEDEM, Z. Consistency in hierarchical database systems. J. ACM 27, I (Jan. 1980), 72-80.
[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.
[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.)
[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.
[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.)
[43]
WEIHL, W.E. Distributed version management for read-only actions. IEEE Trans. Softw. Eng. SE-13, 1 (Jan. 1987), 55-64.
[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.)
[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.
[46]
WEIHL, W., AND LISKOV, B. Implementation of resilient, atomic data types. ACM Trans. Program. Lang. Syst. 17, 2 (Apr. 1985), 244-269.

Cited By

View all

Recommendations

Reviews

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
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.

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)73
  • Downloads (Last 6 weeks)23
Reflects downloads up to 13 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media