The failure and recovery problem for replicated databases

ABSTRACT

A replicated database is a distributed database in which some data items are stored redundantly at multiple sites. The main goal is to improve system reliability. By storing critical data at multiple sites, the system can operate even though some sites have failed. However, few distributed database systems support replicated data, because it is difficult to manage as sites fail and recover. A replicated data algorithm has two parts. One is a discipline for reading and writing data item copies. The other is a concurrency control algorithm for synchronizing those operations. The read-write discipline ensures that if one transaction writes logical data item ×, and another transaction reads or writes x, there is some physical manifestation of that logical conflict. The concurrency control algorithm synchronizes physical conflicts; it knows nothing about logical conflicts. In a correct replicated data algorithm, the physical manifestation of conflicts must be strong enough so that synchronizing physical conflicts is sufficient for correctness. This paper presents a theory for proving the correctness of algorithms that manage replicated data. The theory is an extension of serializability theory. We apply it to three replicated data algorithms: Gifford's “quorum consensus” algorithm, Eager and Sevcik's “missing writes” algorithm, and Computer Corporation of America's “available copies” algorithm.

REFERENCES

• 1: Alsberg, P.A., G.G. Belford, J.D. Day, and E. Grapa, "Multi-copy Resiliency Techniques," Distributed Data Management (J.B. Rothnie, P.A. Bernstein, D.W. Shipman, eds.), IEEE, 1978, pp. 128-176.
• 2: Attar, R., P.A. Bernstein, and N. Goodman, "Site Initialization, Recovery, and Back-up in a Distributed Database System," Proc. 6th Berkeley Workshop, Feb. 1982, pp. 185-202.
• 3: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 4: Bernstein, P.A., N. Goodman, and V. Hadzillacos, "Recovery Algorithms for Database Systems," Proc. 9th IFIPS Congress, Sept. 1983.
• 5: H. Breitwieser , M. Leszak, A distributed transaction processing protocol based on majority consensus, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.224-237, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806701]
• 6: Bernstein, P.A., D.W. Shipman, and W.S. Wong, "Formal Aspects of Serializability in Database Concurrency Control," IEEE Trans. on Software Engineering, SE-5, 3 (may 1979), pp. 203-215.
• 7: Dolev, D., "The Byzantine Generals Strike Again," J. of Algorithms, 3, 1 (1982).
• 8: 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]
• 9: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 10: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588061]
• 13: Micael Hammer , David Shipman, Reliability mechanisms for SDD-1: a system for distributed databases, ACM Transactions on Database Systems (TODS), v.5 n.4, p.431-466, Dec. 1980 [doi>10.1145/320610.320621]
• 14: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 15: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 16: Stearns, R.E., Lewis, P.M., II, and Rosen-krantz, D.J., "Concurrency Controls for Database Systems," Proc. of the 17th Annual Symp. on Foundations of Computer Science, IEEE, 1976, pp. 19-32.
• 17: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 18: Irving L. Traiger , Jim Gray , Cesare A. Galtieri , Bruce G. Lindsay, Transactions and consistency in distributed database systems, ACM Transactions on Database Systems (TODS), v.7 n.3, p.323-342, Sept. 1982 [doi>10.1145/319732.319734]
• 19: Joost S. M. Verhofstad, Recovery Techniques for Database Systems, ACM Computing Surveys (CSUR), v.10 n.2, p.167-195, June 1978 [doi>10.1145/356725.356730]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Management