David K. Gifford
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.
- 1.Eswaran, K.P. et al The Notions of Consistency and Predicate Locks in a Database System, Comm. ACM 19. 11 (November 1976), pp. 624-633. Google Scholar
Digital Library
- 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.Google Scholar
- 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.Google Scholar
- 4.Gray, J.N. Notes on Data Base Operating Systems, in Operating Systems, An Advanced Course, Lecture Notes in Computer Science 60, Springer-Verlag, 1978, pp. 393-481. Google ScholarDigital Library
- 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.Google Scholar
- 6.Lampson, B.W., and Redell, D.D. Experience with Processes and Monitors in Mesa, to appear in Proceedings of the Seventh Symposium on Operating System Principles, ACM Operating Systems Review. Google ScholarDigital Library
- 7.Lampson, B.W., and Sturgis, H.E. Crash Recovery in a Distributed Data Storage System, Comm. ACM, to appear.Google Scholar
- 8.Mitchell, J.G. et al, Mesa Language Manual. CSL Report 79-3, Xerox Palo Alto Research Center, February, 1979Google Scholar
- 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.Google Scholar
- 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-194Google ScholarDigital Library
- 11.Thomas, R.H. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases, ACM Trans. on Database Systems4,2(June 1979), pp. 180-209. Google ScholarDigital Library
Index Terms
- Weighted voting for replicated data
Recommendations
A New Quorum-Based Scheme for Managing Replicated Data in Distributed Systems
We propose a new quorum-based scheme for managing replicated data in distributed systems. We first introduce a concept called difference pair toestablish the basics for cyclic read-write coteries. A simple and efficient model is then presented to ...
Protocol refinement for maintaining replicated data in distributed systems
SPDP '93: Proceedings of the 1993 5th IEEE Symposium on Parallel and Distributed ProcessingData can be replicated to improve availability and performance in distributed systems. To ensure one copy serializability, many protocols have been proposed. Most of these protocols are based on the quorum set approach.However, some of them are ...
Analyzing User-Perceived Dependability and Performance Characteristics of Voting Algorithms for Managing Replicated Data
User-perceived dependability and performance metrics are very different from conventional ones in that the dependability and performance properties must be assessed from the perspective of users accessing the system. In this paper, we develop techniques ...
Comments