A concurrency control algorithm in a distributed environment

ABSTRACT

As a continuation of the POLYPHEME study, the Cii-Honeywell Bull research center has launched a project on co-operating transactional systems with particular attention paid to distributed concurrency control and commitment.

Following the presentation of the application-driven approach being taken, the distributed concurrency control algorithm is described as an improvement of the proposal made by Rosenkrantz, Stearns and Lewis. Salient technical features such as deadlock prevention, wrong aborts, parallel execution, and relation between concurrency control and commitment are detailed. Then the main choices are justified, and the rejected techniques criticized.

REFERENCES

• 1: Adiba, M., J. M. Andrade, P. Decitre, F. Fernandez, Nguyen Gia Toan, "An Experience in Distributed Database System Design and Implementation," International Symposium on Distributed Databases. (Paris: North-Holland, 1980), pp. 67--84.
• 2: Azéma, P., B. Berthomieux, P. Decitre, "The Design and Validation by Petri Nets of a Mechanism for the Invocation of Remote Servers," IFIP Congress, Melbourne, Oct. 1980.
• 3: Bernstein, Philip A., and Nathan Goodman. "Fundamental Algorithms for Concurrency Control in Distributed Database Systems." Technical Report. CCA-80-05, Computer Corporation of America. (Cambridge: Feb. 1980).
• 4: P. A. Bernstein , D. W. Shipman , W. S. Wong, Formal Aspects of Serializability in Database Concurrency Control, IEEE Transactions on Software Engineering, v.5 n.3, p.203-216, May 1979 [doi>10.1109/TSE.1979.234182]
• 5: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 6: Gardarin, Georges, and Brigitte Piot. "Detection and Frequency Evaluation of Concurrency Conflicts." 1st European Conf. on Parallel and Distributed Processing.". Toulouse, France, February 1978, pp. 236--261.
• 7: Gligor, Virgil D., and Susan H. Shattuck. "On Deadlock Detection in Distributed Systems." University of Maryland Computer Science Technical Report 837, December 1979.
• 8: Gray, J., "Notes on Database Operating Systems." Research Report, IBM Research Laboratory, San Jose, February 1978.
• 9: Herman, D., and J. P. Verjus, "An Algorithm for Maintaining the Consistency of Multiple Copies," First International Conference on Distributed Computing Systems, Huntsville, Alabama, October 1979.
• 10: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 11: Le Lann, Gérard, "Algorithms for Distributed Data-sharing Systems Which Use Tickets," 3rd Berkeley Workshop on Distributed Data Management and Computer Networks. San Francisco, August 1978, p. 259.
• 12: Menasce, Daniel, and Richard R. Muntz, "Locking and Deadlock Detection in Distributed Databases," 3rd Berkeley Workshop on Distributed Data Management and Computer Networks. San Francisco, August 1978, pp. 215--232.
• 13: Obermack, Ron, "Global Deadlock Detection Algorithm." Research Report, IBM Research Laboratory, San Jose, June 1980.
• 14: Rosenkrantz, D. J., R. E. Stearns, and P. M. Lewis, "A System Level Concurrency Control for Distributed Database Systems," 2nd Berkeley Workshop on Distributed Data Management Computer Networks. Univ. of California at Berkeley, May 1977, pp. 132--145.
• 15: Wilms, Paul. "An Overview of Update Algorithms in Distributed Databases. Formalization with Nutt's Evaluation Nets." SCOT Research Report #7, Centre de recherche CII-Honeywell-Bull, Grenoble, France.
• 16: SCOT group. "SCOT, Présentation générale des mécanismes." SCOT Research Report #8, Centre de recherche CII-Honeywell-Bull, Grenoble, France.
• 17: SCOT group. "Description du protocol SCOT." Scot Research Report #9, Centre de Recherche CII-Honeywell-Bull, Grenoble, France.
• 18: SDD1 Group. Technical Reports. Computer Corporation of America, Cambridge, Mass., 1980.
• 19: M. Stonebraker, Concurrency Control and Consistency of Multiple Copies of Data in Distributed Ingres, IEEE Transactions on Software Engineering, v.5 n.3, p.188-194, May 1979 [doi>10.1109/TSE.1979.234180]