article

Free Access

Concurrency Control in Distributed Database Systems

Authors:
Philip A. Bernstein

Computer Corporation of America, Cambridge, Massachusetts

Computer Corporation of America, Cambridge, Massachusetts
View Profile

,
Nathan Goodman

Computer Corporation of America, Cambridge, Massachusetts

Computer Corporation of America, Cambridge, Massachusetts
View Profile

Authors Info & Claims

ACM Computing Surveys Volume 13 Issue 2pp 185–221https://doi.org/10.1145/356842.356846

Published:01 June 1981Publication History

ACM Computing Surveys

References

AHO75 AHO, A. V., HOPCROFT, E., AND ULLMAN, J. D. The design and analys~s of computer algorithms, Addison-Wesley, Reading, Mass., 1975. Google Scholar
ALSB76a ALSBERG, P. A, AND DAY, J.D. "A principle for resilient sharing of distributed resources," in Proc. 2nd Int. Conf. Software Eng., Oct. 1976, pp. 562-570. Google ScholarDigital Library
ALSB76b ALSBERG, P. A., BELFORD, G.C., DAY, J. D., AND GRAPLA, E. "Multi-copy resiliency techniques," Center for Advanced Computation, AC Document No. 202, Univ. Illinois at Urbana-Champaign, May 1976.Google Scholar
BADA78 BADAL, D. Z., AND POPEK, G.J. "A proposal for distributed concurrency control for partially redundant distributed data base system," in Proc. 3rd Berkeley Workshop D~str~buted Data Management and Computer Networks, 1978, pp. 273-288Google Scholar
BADA79 BADAL, D. Z. "Correctness of concurrency control and imphcations in distributed databases," in Proc COMPSAC 79 Conf., Chicago, Ill., Nov. 1979.Google Scholar
BADA80 BADAL, D.Z. "On the degree of concurrency provided by concurrency control mechanisms for distributed databases," in Proc. Int Syrup. D~stributed Databases, Versailles, France, March 1980.Google Scholar
BAYE80 BAYER, R., HELLER, H., AND REISER, A. "Parallelism and recovery in database systems," A CM Trans. Database Syst. 5, 2 (June 1980), 139-156. Google ScholarDigital Library
BELF76 BI~LFORD, G. C., SCHWARTZ, P. S., AND SLUIZER, S. "The effect of back-up strategy on database availability," CAC Document No. 181, CCTCWAD Document No. 5515, Center for Advanced Computation, Univ. Illmom at Urbana- Champaign, Urbana, Feb. 1976.Google Scholar
BERN78a BERNSTEIN, P. A., GOODMAN, N., ROTH- NIE, J B., AND PAPADIMITRIOU, C. A. "The concurrency control mechanism of SDD-I: A system for distributed databases (the fully redundant case)," IEEE Trans. Softw. Eng. SE-4, 3 (May 1978), 154-168.Google ScholarDigital Library
BERN79a BERNSTEIN, P. A., AND GOODMAN, N. "Approaches to concurrency control in dmtributed databases," in Proc. 1979 Natl. Computer Conf., AFIPS Press, Arlington, Va., June 1979.Google Scholar
BERN79b BERNSTEIN, P. A., SHIPMAN, D. W., AND WONG, W.S. "Formal Aspects of Senalizability in Database Concurrency Control," IEEE Trans. Softw Eng. SE-5, 3 (May 1979), 203-215.Google ScholarDigital Library
BERN80a BERNSTEIN, P. A., AND GOODMAN, N. "Timestamp based algorithms for concurrency control in distributed database systems," Proc 6th Int. Conf. Very Large Data Bases, Oct. 1980.Google Scholar
BERN80b BERNSTEIN, P. A., GOODMAN, N., AND LAI, M.Y. "Two Part Proof Schema for Database Concurrency Control," in Proc 5th Berkeley Workshop D~str~buted Data Management and Computer Networks, Feb. 1980.Google Scholar
BERN80c BERNSTEIN, P. A, AND SHIPMAN, D. W "The correctness of concurrency control mechanisms in a system for dtstributed databases (SDD-1)," in ACM Trans. Database Syst. 5, 1 (March 1980), 52-68. Google ScholarDigital Library
BERN80d BERNSTEIN, P, SHIPMAN, D. W., AND ROTHNIE, J.B. "Concurrency control in a system for distributed databases (SDD- 1)," in ACM Trans. Database Syst 5, 1 (March 1980), 18-51. Google ScholarDigital Library
BERN81 BERNSTEIN, P. A, GOODMAN, N., WONG, E, REEVE, C. L., AND ROTHNIE, J. B. "Query processing m SDD-I," ACM Trans. Database Syst. 6, 2, to appear. Google Scholar
BREI79 BREITWIESER, H., AND KERSTEN, U. "Transaction and catalog management of the distributed file management system DISCO," in Proc. Very Large Data Bases, Rio de Janerio, 1979Google Scholar
BRIN73 BRINCH-HANSEN, P. Operating system principles, Prentice-Hall, Englewood Cliffs, N. J., 1973. Google Scholar
CASA79 CASANOVA, M. A. "The concurrency control problem for database systems," Ph.D. dissertation, Harvard Univ., Tech. Rep. TR-17-79, Center for Research in Computing Technology, 1979.Google Scholar
CHAM74 CHAMBERLIN, D. D., BOYCE, R. F., AND TRAIGER, I.L. "A deadlock-free scheme for resource allocation in a database envLronment," Info. Proc. 74, North-Holland, Amsterdam, 1974.Google Scholar
CHEN80 CHENG, W. K., AND BELFORD, G. C. "Update SynchronLzation in Distributed Databases," in Proc. 6th Int. Conf. Very Large Data Bases, Oct. 1980.Google Scholar
DEPP76 DEPPE, M. E., AND FRY, J. P. "Distributed databases' A summary of research," in Computer networks, vol. 1, no. 2, North-Holland, Amsterdam, Sept. 1976.Google Scholar
DIJK71 DIJKSTRA, E.W. "Hmrarchical ordering of sequential processes," Acta Inf. 1, 2 (1971), 115-138.Google ScholarDigital Library
ELLI77 ELLIS, C.A. "A robust algorithm for updating duphcate databases," in Proc 2nd Berkeley Workshop D~stnbuted Databases and Computer Networks, May 1977.Google Scholar
ESWA76 ESWARAN, K. P., GRAY, J. N., LORIE, R. A., AND TRAIGER, I.L. "The notions of consistency and predicate locks in a database system." Commun. ACM 19, 11 (Nov. 1976), 624-633. Google ScholarDigital Library
GARC78 GARCIA-MOLINA, H "Performance comparisons of two update algorithms for distributed databases," in Proc. 3rd Berkeley Workshop D~stnbuted Databases and Computer Networks, Aug. 1978.Google Scholar
GARC79a GARCIA-MOLINA, H. "Performance of update algorithms for replicated data in a (hstributed database," Ph.D. dmsertatlon, Computer Science Dept., Stanford Umv., Stanford, Calif., June 1979. Google Scholar
GARC79b GARCIA-MOLINA, I-I. "A concurrency control mechanism for distributed data bases winch use centralized locking controllers," in Proc. 4th Berkeley Workshop D~str~buted Databases and Computer Networks, Aug. 1979.Google Scholar
GARC79c GARCIA-MOLINA, H. "CentralLzed control update algorithms for fully redundant distributed databases," in Proe. 1st Int. Conf. D~stributed Computing Systems (IEEE), New York, Oct. 1979, pp. 699- 705.Google Scholar
GARD77 GARDARIN, G., AND LEBAUX, P. "Scheduling algorithms for avoiding inconsistency in large databases," in Proc. 1977 Int. Conf. Very Large Data Bases (IEEE), New York, pp. 501-516.Google Scholar
GELE78 GELEMBE, E., AND SEVCIK, K. "Analysis of update synchronization for multiple copy databases," in Proc. 3rd Berkeley Workshop Distributed Databases and Computer Networks, Aug. 1978.Google Scholar
GIFF79 GIFFORD, D. K. "Weighted voting for rephcated data," in Proc. 7th Symp. Operating Systems Principles, Dec. 1979. Google Scholar
GRAY75 GRAY, J. N., LORIE, R. A., PUTZULO, G. R., AND TRAIGER, I.L. "Granularity of locks and degrees of consistency in a shared database," IBM Res. Rep. RJ1654, Sept. 1975.Google Scholar
GRAY78 GRAY, J.N. "Notes on database operating systems," in Operating Systems: An Advanced Course, vol. 60, Lecture Notes in Computer Science, Springer-Verlag, New York, 1978, pp. 393-481. Google Scholar
HAMM80 HAMMER, M. M., AND SHIPMAN, D. W. "Reliabihty mechanisms for SDD-I: A system for distributed databases," ACM Trans. Database Syst. 5, 4 (Dec. 1980), 431-466. Google ScholarDigital Library
HEWI74 HEWlTT, C.E. "Protection and synchronization in actor systems," Working Paper No. 83, M.I.T. Artificial Intelligence Lab., Cambridge, Mass., Nov. 1974.Google Scholar
HOAR74 HOARE, C. A.R. "Monitors. An operating system structuring concept," Commun. ACM 17, 10 (Oct. 1974), 549-557. Google ScholarDigital Library
HOLT72 HOLT, R.C. "Some deadlock propertms of computer systems," Comput. Surv. 4, 3 (Dec. 1972) 179-195. Google ScholarDigital Library
KANE79 KANEKO, A., NISHIHARA, Y., TSURUOKA, K., AND HATTORI, M. "Logical clock synchronization method for duplicated database control," in Proe. 1st Int. Conf. D~stributed Computing Systems (IEEE), New York, Oct. 1979, pp. 601-611.Google Scholar
KAWA79 KAWAZU, S, MINAMI, ITOH, S., AND TER- ANAKA, K. "Two-phase deadlock detection algorithm in distributed databases," in Proc. I979 Int. Conf. Very Large Data Bases (IEEE), New York. Google Scholar
KING74 KING, P. F., AND COLLMEYER, A J. "Database sharing--an efficient method for supporting concurrent processes," in Proc. 1974 Nat. Computer Conf., vol. 42, AFIPS Press, Arlington, Va., 1974.Google Scholar
KUNG79 KUN6, H. T., AND PAPADIMITRIOU, C. H. "An optimality theory of concurrency control for databases," in Proc. 1979 ACM-SIGMOD Int. Conf Management of Data, June 1979. Google Scholar
KUNG81 KUNG, H. T., AND ROBINSON, J.T. "On optimistic methods for concurrency control," ACM Trans. Database Syst. 6, 2, (June 81), 213-226. Google Scholar
LAMP76 LAMPSON, B., AND STURGIS, H. "Crash recovery in a chstrlbuted data storage system," Tech. Rep., Computer Science Lab., Xerox Palo Alto Research Center, Palo Alto, Calif., 1976.Google Scholar
LAMP78 LAMPORT, L. "Time, clocks and ordering of events in a distributed system," Com. mun. ACM 21, 7 (July 1978), 558-565. Google ScholarDigital Library
LELA78 LELANN, G. "Algorithms for distributed data-sharing sytems which use tickets," m Proc. 3rd Berkeley Workshop Distributed Databases and Computer Networks, Aug. 1978.Google Scholar
LIN79 LIN, W. K. "Concurrency control in multiple copy distributed data base system," in Proc 4th Berkeley Workshop Distributed Data Management and Computer Networks, Aug. 1979.Google Scholar
MENA79 MENASCE, D. A., AND MUNTZ, R. R. "Locking and deadlock detection in dmtributed databases," IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 195-202.Google ScholarDigital Library
MENA80 MENASCE, D. A., POPEK, G. J., AND MUNTZ, R.R. "A locking protocol for resource coordination in distributed databases," A CM Trans. Database Syst. 5, 2 (June 1980), 103-138. Google ScholarDigital Library
MINO78 MINOURA, T. "Maximally concurrent transaction processing," in Proc. 3rd Berkeley Workshop D~stnbuted Databases and Computer Networks, Aug. 1978.Google Scholar
MINO79 MINOURA, T. "A new concurrency control algorithm for distributed data base systems," in Proc. 4th Berkeley Workshop D~stributed Data Management and Computer Networks, Aug. 1979.Google Scholar
MONT78 MONTGOMERY, W. A. "Robust concurrency control for a distributed information system," Ph.D. dissertation, Lab. for Computer Science, M.I.T., Cambridge, Mass, Dec. 1978.Google Scholar
PAPA77 PAPADIMITRIOU, C. H., BERNSTEIN, P A, AND ROTHNIE, J. B. "Some computational problems related to database concurrency control," in Proc. Conf. Theoret. wal Computer Scwnce, Waterloo, Ont., Canada, Aug. 1977.Google Scholar
PAPA79 PAPADIMITRIOU, C. H. "Serial~zability of concurrent updates," J. A CM 26, 4 (Oct. 1979), 631-653. Google Scholar
RAHI79 RAHIMI, S K., AND FRANTS, W.R. "A posted update approach to concurrency control in distributed database systems," in Proc. 1st Int. Conf. D~str~buted Computing Systems (IEEE), New York, Oct. 1979, pp. 632-641.Google Scholar
RAMI79 RAMIREZ, R. J, AND SANTORO, N. "Distributed control of updates in multiple-copy data bases: A time optimal algorithm," in Proc. 4th Berkeley Workshop Dtstributed Data Management and Computer Networks, Aug. 1979.Google Scholar
REED78 REED, D.P. "Naming and synchronization m a decentralized computer system~ Ph.D. dissertation, Dept. of Electrical Engineering, M.I.T., Cambridge, Mass., Sept., 1978.Google Scholar
REIS79a REIS, D. "The effect of concurrency control on database management system performance," Ph.D. dissertation, Computer Science Dept., Univ. California, Berkeley, April 1979.Google Scholar
REIS79b REIS, D. "The effects of concurrency control on the performance of a distributed database management system," in Proc. 4th Berkeley Workshop Dtstrtbuted Data Management and Computer Networks, Aug. 1979.Google Scholar
ROSE79 ROSEN, E.C. "The updating protocol of the ARPANET's new routing algorithm: A case study in maintaining identical copies of a changing distributed data base," in Proc. 4th Berkeley Workshop Dtstnb. uted Data Management and Computer Networks, Aug. 1979.Google Scholar
ROSE78 ROSENKRANTZ, D. J., STEARNS, R E., AND LEWIS, P.M. "System level concurrency control for distributed database systems," A CM Trans. Database Syst. 3, 2 (June 1978), 178-198. Google ScholarDigital Library
ROTH77 ROTHNIE, J. B., AND GOODMAN, N. "A survey of research and development in distributed databases systems," in Proc 3rd Int. Conf. Very Large Data Bases (IEEE), Tokyo, Japan, Oct. 1977.Google Scholar
SCHL78 SCHLAGETER, G. "Process synchromzation in database systems." A CM Trans. Database Syst. 3, 3 (Sept. 1978), 248-271. Google Scholar
SEQU79 SEQUIN, J., SARGEANT, G., AND WILNES, P. "A majority consensus algorithm for the consmtency of duplicated and distributed information," in Proc. 1st Int. Conf. Distributed Computing Systems (IEEE), New York, Oct. 1979, pp. 617-624.Google Scholar
SHAP77a SHAPIRO, R. M., AND MILLSTEIN, R. E. "Rehability and fault recovery in distributed processing," in Oceans '77 Conf Record, vol II, Los Angeles, 1977.Google Scholar
SHAP77b SHAPIRO, R. M., AND MILLSTEIN, R. E. "NSW reliability plan," Massachusetts Tech. Rep. 7701-1411, Computer Associates, Wakefield, Mass., June 1977.Google Scholar
SILB80 SILBERSCHATZ, A., AND KEDEM, Z. "Consistency in hierarchical database systems," J. ACM 27, 1 (Jan. 1980), 72- 80. Google ScholarDigital Library
STEA76 STEARNS, R. E., LEWIS, P. M. II, AND ROSENKRANTZ, D.J. "Concurrency controis for database systems," in Proc. 17th Syrup. Foundatmns Computer Science (IEEE), 1976, pp. 19-32.Google Scholar
STEA81 STEARNS, R. E., AND ROSENKRANTZ, J. "Distributed database concurrency controls using fore-values," in Proc 1981 SIGMOD Conf. (ACM). Google Scholar
STON77 STONEBRAKER, M., AND NEUHOLD, E. "A distributed database version of INGRES," in Proc. 2nd Berkeley Workshop D~stributed Data Management and Computer Networks, May 1977.Google Scholar
STON79 STONEBRAKER, M. "Concurrency control and consistency of multiple copies of data in distributed INGRES, IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 188-194.Google ScholarDigital Library
THOM79 THOMAS, R.H. "A solution to the concurrency control problem for multiple copy databases," in Proc. 1978 COMP- CON Conf. (IEEE), New York.Google Scholar
VERH78 VERHOFSTAD, J. S. M. "Recovery and crash resmtance in a filing system," in Proc. SIGMOD Int Conf. Management ofData (ACM), New York, 1977, pp 158- 167. Google Scholar
1 Cert~fwrs: BADA79, BAYE80, CASA79, KUNGS1, PAPA79, THOM79Google Scholar
2 Concurrency control theory: BERN79b, BERNS0C, CASA79, ESWA76, KUNG79, MINO78, PAPA77, PAPA79, SCHL78, SILB80, STEA76Google Scholar
3 Performance: BADA80, GARC78, GARC79a, GARC79b, GELE78, REIS79a, RExs79b, ROTH77Google Scholar
4 Reliability General: ALSB76a, ALSB76b, BELF76, BERN79a, HAMMS0, LAMP76 Two-phase commW. HAMMS0, LAMP76Google Scholar
5 Timestamp-ordered scheduling (T/O) eneral: BADA78, BERN78a, BERN80a, BERN80b, BERN80d, LELA78, LIN79, RAMI79 Thomas' Wr~te Rule: THOM79 Multivers~on t~mestamp ordering: MONT78, REED78 T~mestamp and clock management: LAMP78, THOM79Google Scholar
6 Two-phase locking (2PL) General. BERN79b, BREI79, ESWA76, GARD77, GRAY75, GRAY78, PAPA79, SCHL78, SILBS0, STEA81 D~str~buted 2PL: MENA80, MINO79, ROSE78, STON79 Primary copy 2PL: STOS77, STO~79 Centralized 2PL: ALSB76a, ALSB76b, GARc79b, GARC79C Voting 2PL: GIFF79, SEQU79, THOM79 Deadlock detection/prevention: GRAY78, KING74, KAWA79, ROSE78, STON79Google Scholar

Index Terms

Concurrency Control in Distributed Database Systems

Recommendations

System level concurrency control for distributed database systems

A distributed database system is one in which the database is spread among several sites and application programs “move” from site to site to access and update the data they need. The concurrency control is that portion of the system that responds to ...
Read More
Optimistic concurrency control algorithms for distributed database systems
Read More
Concurrency control architectures in distributed database systems
Read More

Comments

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

Published in
ACM Computing Surveys Volume 13, Issue 2
June 1981
100 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/356842
Editor:
Adele Goldberg
Issue’s Table of Contents
Copyright © 1981 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
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 1 June 1981
Published in csur Volume 13, Issue 2

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Qualifiers
- article
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 829
  Total Citations
  View Citations
- 13,345
  Total Downloads
- Downloads (Last 12 months)1,565
- Downloads (Last 6 weeks)170
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Concurrency Control in Distributed Database Systems

ACM Computing Surveys

References

Cited By

Index Terms

Recommendations

System level concurrency control for distributed database systems

Optimistic concurrency control algorithms for distributed database systems

Concurrency control architectures in distributed database systems

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF Format

eReader

Digital Edition

Caption

Concurrency Control in Distributed Database Systems

ACM Computing Surveys

References

Cited By

Index Terms

Recommendations

System level concurrency control for distributed database systems

Optimistic concurrency control algorithms for distributed database systems

Concurrency control architectures in distributed database systems

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Funding Sources

Article Metrics

Other Metrics

PDF Format

eReader

Digital Edition

Share this Publication link

Share on Social Media