Weighted voting for replicated data
David Kenneth Gifford · ACM Symposium on Operating Systems Principles (SOSP) · 1979
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.
Cited by 1,323 works. doi:10.1145/800215.806583 Open-access PDF
Authors
References
- The notions of consistency and predicate locks in a database system
- Notes on data base operating systems
- Crash Recovery in a Distributed Data Storage System
- Experience with processes and monitors in Mesa
- A Majority consensus approach to concurrency control for multiple copy databases
- Granularity of locks and degrees of consistency in a shared data base
- Separating data from function in a distributed file system
- Concurrency Control and Consistency of Multiple Copies of Data in Distributed Ingres
- Experience with processes and monitors in Mesa (Summary)
- A Majority Consensus Approach to Concurrency Control for Multiple Copy Data Bases