Abstract
A major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. We suggest addressing this problem by implementing applications in terms of abstract data types with two properties: Their objects are atomic (they provide serializability and recoverability for activities using them) and resilient (they survive hardware failures with acceptably high probability). We define what it means for abstract data types to be atomic and resilient. We also discuss issues that arise in implementing such types, and describe a particular linguistic mechanism provided in the Argus programming language.
- 1 BERNSTEIN, P., AND GOODMAN, N. Concurrency control algorithms for multiversion database systems. In ACM Symposium on Principles of Distributed Computing, (Ottawa, Aug. 1982), ACM, New York, 209-215. Google Scholar
- 2 BERNSTEIN, P., GOODMAN, N., AND LAI, M. Two-part proof schema for database concurrency control. In Proceedings of the 5th Berkeley Workshop on Distributed Data Management and Computer Networks, (Feb. 1981), 71-84.Google Scholar
- 3 BEST, E., AND RANDELL, B. A formal model of atomicity in asynchronous systems. Acta Inf. 16 (1981), 93-124.Google Scholar
- 4 DAHL, O.-J., ET AL. The Simula 67 common base language. Publication No. S-22, Norwegian Computing Center, Oslo, 1970.Google Scholar
- 5 DAVIES, C. T. Recovery semantics for a DB/I)C system. In Proceedings of the 1973 ACM National Conference, (1973), ACM, New York, 136-141. Google Scholar
- 6 DAVIES, C.T. Data processing spheres of control. IBM Syst. J. 17, 2 (1978), 179-198.Google Scholar
- 7 ELLIS, C. Concurrent search and insertion in 2-3 trees. Acta Inf. 14 (1980), 63-86.Google Scholar
- 8 ESWARAN, K. P., GRAY, J. N., LOR1E, R. A., AND TRAIGER, I.L. The notion of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624-633. Google Scholar
- 9 GIFI~ORD, D. Weighted voting for replicated data. In Proceedings of the 7th ACM SIGOPS Symposium on Operating Systems Principles, (Dec. 1979), ACM, New York, 150-162. Google Scholar
- 10 GRAY, J.N., Notes on database operating systems. In Lecture Notes in Computer Science 60, GoDs and Hartmanis, Eds., Springer-Verlag, Berlin, 1978, 393-481. Google Scholar
- 11 GRAY, J. N., ET AL. The recovery manager of the System R database manager. ACM Comput. Surv. 13, 2 (June 1981), 223-242. Google Scholar
- 12 GUTTAO, J., HOROWITZ, E., AND MUSSER, D. Abstract data types and software validation. Commun. ACM 21, 12 (Dec. 1978), 1048-1064. Google Scholar
- 13 HERLIHY, M.P. Replication methods for abstract data types. Ph.D dissertation, Tech. Rep. MIT/LCS/TR-319, MIT Laboratory for Computer Science, May 1984. Google Scholar
- 14 HOARE, C. A.R. Monitors: An operating system structuring concept. Commun. ACM 17, 10 (Oct. 1974), 549-557. Google Scholar
- 15 KORTH, H.F. Locking primitives in a database system. J. ACM 30, I (Jan. 1983), 55-79. Google Scholar
- 16 KUNG, H. T., AND ROBINSON, J.T. On optimistic methods for concurrency control ACM Trans. Database Syst. 6, 2 (June 1981), 213-226. Google Scholar
- 17 LAMPSON, B., AND REDELL, D. Experience with processes and monitors in Mesa. Commun. ACM 23, 2 (Feb. 1980), 105-117. Google Scholar
- 18 LAMPSON, B. Atomic transactions. In Distributed Systems: Architecture and Implementation. Lecture Notes in Computer Science 105, GoDs and Hartmanis, Eds., Springer-Verlag, Berlin, 1981, 246-265. Google Scholar
- 19 LISKOV, B. AND ZILLES, S.N. Programming with abstract data types. In Proceedings ACM SIGPLAN Conference on Very High-Level Languages. SIGPLAN Not. 9, 4 (Apr. 1974), 50-59. Google Scholar
- 20 L1SKOV, B., SNYDER, A., ATKINSON, R. R., AND SCHAFFERT, J.C. Abstraction mechanisms in CLU. Commun. ACM 20, 8 (Aug. 1977), 564-576. Google Scholar
- 21 LISKOV, B., ET AL. CLU reference manual. In Lecture Notes in Computer Science 114, GoDs and Hartmanis, Eds., Springer-Verlag, Berlin, 1981. Google Scholar
- 22 LISKOV, B., AND SCHEIFLER, R. Guardians and actions: Linguistic support for robust, distributed programs. ACM Trans. Programm. Lang. Syst. 5, 3 (July 1983), 381-404. Google Scholar
- 23 Moss, J. E. B. Nested transactions: An approach to reliable distributed computing. Ph.D dissertation. Tech. Rep. MIT/LCS/TR-260, MIT Laboratory for Computer Science, 1981. Google Scholar
- 24 PAPADIM1TRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct. 1979), 631-653. Google Scholar
- 25 PAXTON, W. A client-based transaction system to maintain data integrity. In Proceedings of the 7th ACM SIGOPS Symposium on Operating Systems Principles, (Dec. 1979), ACM, New York, 18-23. Google Scholar
- 26 REED, D.P. Naming and synchronization in a decentralized computer system. Ph.D dissertation. Tech. Rep. MIT/LCS/TR-205, MIT Laboratory for Computer Science, 1978. Google Scholar
- 27 SCHWARZ, P., AND SPECTOR, A. Synchronizing shared abstract types. ACM Trans. Comput. Syst. 2, 3 (Aug 1984), 223-250. Google Scholar
- 28 STIJRGIS, H., MITCHELL, J., AND ISRAEL, J. Issues in the design and use of a distributed file system. Oper. Syst. Rev. 14, 3 (July 1980), 55-69. Google Scholar
- 29 WEIHL, W. E., AND LISKOV, B.H. Specification and implementation of resilient, atomic data types. In Proceedings of the SIGPLAN '83 Symposium on Programming Language Issues in So{tware Systems, (San Francisco, June 1983), ACM, New York, 53-64. Google Scholar
- 30 WEIHL, W.E. Data-dependent concurrency control and recovery. In Proceedings of the 2nd Annual ACM Symposium on Principles o{ Distributed Computing (Montreal, Aug. 1983), ACM, New York, 63-75. Google Scholar
- 31 WEIHL, W.E. Specification and implementation of atomic data types. Ph.D dissertation. Tech. Rep. MIT/LCS/TR-314, MIT Laboratory for Computer Science, Mar. 1984. Google Scholar
Index Terms
- Implementation of resilient, atomic data types
Recommendations
Specification and implementation of resilient, atomic data types
SIGPLAN '83: Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systemsA major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. We suggest addressing this problem by implementing applications in terms of abstract data types with two properties: ...
Specification and implementation of resilient, atomic data types
A major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. We suggest addressing this problem by implementing applications in terms of abstract data types with two properties: ...
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 ...
Comments