Maintaining availability in partitioned replicated databases

ABSTRACT

In a replicated database, a data item may have copies residing on several sites. A replica control protocol is necessary to ensure that data items with several copies behave as if they consist of a single copy, as far as users can tell. We describe a new replica control protocol that allows the accessing of data in spite of site failures and network partitioning. This protocol provides the database designer with a large degree of flexibility in deciding the degree of data availability, as well as the cost of accessing data.

REFERENCES

• 1: 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]
• 2: Philip A. Bernstein , Nathan Goodman, The failure and recovery problem for replicated databases, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.114-122, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806714]
• 3: Philip A. Bernstein , Nathan Goodman, An algorithm for concurrency control and recovery in replicated distributed databases, ACM Transactions on Database Systems (TODS), v.9 n.4, p.596-615, Dec. 1984 [doi>10.1145/1994.2207]
• 4: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 5: CHEUNG, D., AND KAMEDA, W. Optimal decentralized termination protocols for partition failures. LCCR TR 86-1, Laboratory for Computer and Communication Research, Simon Fraser Univ., Burnaby, B.C., Canada, Jan. 1986.
• 6: CHUNG-KUO, C., AND GOUDA, M. Independent recovery. In Proceedings of the 6th Symposium on Relaibility in Distiributed Software and Database Systems (Williamsburg, Va. Mar. 1987). IEEE, New York, 1987, pp. 93-104.
• 7: Brian A Coan , Brian M Oki , Elliot K Kolodner, Limitations on database availability when networks partition, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.187-194, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10606]
• 8: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• 9: Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983 [doi>10.1145/319989.319992]
• 10: Amr El Abbadi, A Paradigm for Concurrency Control Protocols for Distributed Databases, Cornell University, Ithaca, NY, 1987
• 11: Amr El Abbadi , Sam Toueg, Availability in partitioned replicated databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.240-251, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15418]
• 12: Amr El Abbadi , Dale Skeen , Flaviu Cristian, An efficient, fault-tolerant protocol for replicated data management, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.215-229, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325443]
• 13: 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]
• 14: 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]
• 15: 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]
• 16: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 17: HADZ~LACOS, V. Issues of fault tolerance in concurrent computations. Tech. Rep. 11-84, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass. (june i984).
• 18: Maurice Herlihy, Dynamic quorum adjustment for partitioned data, ACM Transactions on Database Systems (TODS), v.12 n.2, p.170-194, June 1987 [doi>10.1145/22952.22953]
• 19: Thomas A. Joseph , Kenneth P. Birman, Low cost management of replicated data in fault-tolerant distributed systems, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.54-70, Feb. 1986 [doi>10.1145/6306.6309]
• 20: 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]
• 21: K J Perry , S Toueg, Distributed agreement in the presence of processor and communication faults, IEEE Transactions on Software Engineering, v.12 n.3, p.477-482, March 1986
• 22: David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
• 23: SKEEN, D. Crash recovery in a distributed database management system. Ph.D. thesis, Memo. UCB/ERL M82/45, Electronics Research Lab., Univ. California, Berkeley, 1982.
• 24: Dale Skeen , David D. Wright, Increasing availability in partitioned database systems, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588054]
• 25: WRIGHT, D. Managing distributed databases in partitioned networks. TR83-572, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., Sept. 1983.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems
      D.4.5 Reliability
          Subjects: Fault-tolerance

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design, Performance, Reliability