Abstract
A “majority consensus” algorithm which represents a new solution to the update synchronization problem for multiple copy databases is presented. The algorithm embodies distributed control and can function effectively in the presence of communication and database site outages. The correctness of the algorithm is demonstrated and the cost of using it is analyzed. Several examples that illustrate aspects of the algorithm operation are included in the Appendix.
- 1 SHAPIRO, R.M., AND MILLSTEIN, R.E. The NSW reliability plan. Rep. CA-7701.1411, Massachusetts Computer Associates, June 1977.]]Google Scholar
- 2 ROTHNIE, J.B., GOODMAN, N., AND BERNSTEIN, P.A. The redundant update methodology of SDD-I: A system for distributed data bases (the fully redundant case). Tech. Rep. CCA-77-02, Computer Corp. of America, Cambridge, Mass., June 1977.]]Google Scholar
- 3 ALSBERG, P.A., AND DAY, J.D. A principle for resilient sharing of distributed resources. Rep. from Ctr. for Advanced Comput., U. of Illinois at Urbana-Champaign, Urbana, Ill., 1976.]]Google Scholar
- 4 HENDERSON, JR., D.A., AND MYER, T.H. Issues in message technology. Proc. Fifth Data Communication Syrup., Snowbird, Utah, Sept. 1977, pp. 6-1-6-9.]] Google ScholarDigital Library
- 5 ROBERTS, L.G., AND WESSLER, B.D. Computer network development to achieve resource sharing. Proc. AFIPS 1970 SJCC, AFIPS Press, Montvale, N.J., pp. 543-549.]]Google Scholar
- 6 METCALFE, R., AND BOGGS, D. Ethernet: Distributed packet switching for local computer networks. Comm. ACM 19, 7 (July 1976), 395-404.]] Google ScholarDigital Library
- 7 CERF, V., AND KAHN, R. A protocol for packet network interconnection. IEEE Trans. Comm. Comm-22, 5 (May 1974), 637-648.]]Google ScholarCross Ref
- 8 JOHNSON, P., AND THOMAS, R. The maintenance of duplicate data bases. Network Information Center (NIC) Document #31507, ARPA Network Working Group Request for Comments (RFC) ~77, Jan. 1975.]] Google Scholar
- 9 ESWAREN, K.P., GRAY, J.N., LORIE, B.A., AND TRAIGEN, I.L. The notions of consistency and predicate locks in a database system. Comm. ACM 19, 11 (Nov. 1976), 624-633.]] Google ScholarDigital Library
- 10 I~MPORT, L. Time, clocks and the ordering of events in a distributed system. Rep. CA-7603-2911, Massachusetts Computer Associates, March 1976; also submitted to Comm. ACM.]]Google Scholar
Index Terms
- A Majority consensus approach to concurrency control for multiple copy databases
Recommendations
An Optimistic Locking Technique for Concurrency Control in Distributed Databases
A method called optimistic method with dummy locks (ODL) is suggested for concurrency control in distributed databases. It is shown that by using long-term dummy locks, the need for the information about the write sets of validated transactions is ...
Concurrency Control in Distributed Databases Through Time Intervals and Short-Term Locks
A method for concurrency control in distributed database management systems that increases the level of concurrent execution of transactions, called ordering by serialization numbers (OSN), is proposed. The OSN method works in the certifier model and ...
Distributed Concurrency Control Based on Limited Wait-Depth
The performance of high-volume transaction processing systems for business applications is determined by the degree of contention for hardware resources as well as for data. Hardware resource requirements may be met cost-effectively with a data-...
Comments