Weighted voting for replicated data

TLDR

The algorithm assigns votes to each replica, uses read and write quorums whose sizes sum to more than the total votes to guarantee quorum intersection, tracks versions to identify current copies, ensures serial consistency, permits temporary no‑vote copies, and has been implemented in the Violet application system. By selecting appropriate values for r, w, and the voting configuration, the system can tune the reliability and performance of replicated files.

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.