Weighted voting for replicated data

ABSTRACT

In a new algorithm for maintaining replicated data, every copy of a replicated file is assigned some number of votes. Every transaction collects a read quorum of rvotes to read a file, and a write quorum of wvotes to write a file, such that r+w is greater than the total number of votes assigned to the file. This ensures that there is a non-null intersection between every read quorum and every write quorum. Version numbers make it possible to determine which copies are current. The reliability and performance characteristics of a replicated file can be controlled by appropriately choosing r, w, and the file's voting configuration. The algorithm guarantees serial consistency, admits temporary copies in a natural way by the introduction of copies with no votes, and has been implemented in the context of an application system called Violet.

REFERENCES

• 1: 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]
• 2: Gifford, D.K. Violet, An Experimental Decentralized System, Integrated Office System Workshop, IRIA, Rocquencourt, France, November, 1979. Available as CSL Report 79-12, Xerox Palo Alto Research Center, 1979.
• 3: Gray, J.N. et al Granularity of Locks and Degrees of Consistency in a Shared Data Base, in Modeling in Data Base Management Systems, North Holland Publishing, 1976, pp. 365-394.
• 4: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 5: Israel, J.E., Mitchell, J.G., and Sturgis, H.E. Separating Data From Function in a Distributed File System, Second International Symposium on Exploratory Systems, IRIA, Rocquencourt, France, October, 1978.
• 6: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa (Summary), Proceedings of the seventh ACM symposium on Operating systems principles, p.43-44, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806568]
• 7: Lampson, B.W., and Sturgis, H.E. Crash Recovery in a Distributed Data Storage System, Comm. ACM, to appear.
• 8: Mitchell, J.G. et al, Mesa Language Manual. CSL Report 79-3, Xerox Palo Alto Research Center, February, 1979
• 9: Rothnie, J.B., Goodman, N., and Bernstein, P.A., The Redundant Update Methodology of SDD-1: A System for Distributed Databases (The Fully Redundant Case), Rep. No. CCA-77-02, Computer Corporation of America, 1977.
• 10: Stonebraker, M. Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES, IEEE Trans. on Soft. Eng.5. 3(May 1979), pp. 188-194
• 11: 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]

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

General Terms:
Algorithms, Human Factors, Management

Keywords:
Computer network, File suite, File system, Locking, Quorum, Replicated data, Representative, Transaction, Weak representative, Weighted voting