Weighted Voting for Replicated Data

Weighted Voting for Replicated Data

1979 | David K. Gifford
This paper presents a new algorithm for maintaining replicated data using weighted voting. The algorithm assigns a number of votes to each copy of a replicated file. Every transaction collects a read quorum of r votes and a write quorum of w votes, 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 are used to determine which copies are current. The algorithm guarantees serial consistency, allows temporary copies to be introduced naturally, and has been implemented in the Violet system. The algorithm's key features include the ability to control the reliability and performance of replicated files by adjusting r, w, and the voting configuration. It operates correctly even with inaccessible copies and runs on top of a transactional file system with minimal additional machinery. The algorithm separates consistency considerations from replication, resulting in a conceptually simple approach that guarantees serial consistency. The algorithm introduces weak representatives, which have no votes and can be used to improve performance. It also includes refinements such as lock compatibility, lower degrees of consistency, and the ability to reassign votes. The algorithm is implemented in the Violet system, which is a decentralized data management system. The algorithm has been tested and shown to handle various scenarios, including the problem of transaction timeouts and the need for read locks to be released before commit. The algorithm's performance is evaluated, and it is shown that the number of reads and writes are inherent to the algorithm, while the number of messages and round-trip delay times are due to the implementation using DFS. The algorithm is demonstrated to provide serial consistency, and the paper concludes that the algorithm offers many benefits not provided by previous solutions. The algorithm's approach to weighted voting has potential applications beyond replication algorithms, particularly in scenarios where decisions must be made by cooperating nodes with different probabilities of being correct.This paper presents a new algorithm for maintaining replicated data using weighted voting. The algorithm assigns a number of votes to each copy of a replicated file. Every transaction collects a read quorum of r votes and a write quorum of w votes, 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 are used to determine which copies are current. The algorithm guarantees serial consistency, allows temporary copies to be introduced naturally, and has been implemented in the Violet system. The algorithm's key features include the ability to control the reliability and performance of replicated files by adjusting r, w, and the voting configuration. It operates correctly even with inaccessible copies and runs on top of a transactional file system with minimal additional machinery. The algorithm separates consistency considerations from replication, resulting in a conceptually simple approach that guarantees serial consistency. The algorithm introduces weak representatives, which have no votes and can be used to improve performance. It also includes refinements such as lock compatibility, lower degrees of consistency, and the ability to reassign votes. The algorithm is implemented in the Violet system, which is a decentralized data management system. The algorithm has been tested and shown to handle various scenarios, including the problem of transaction timeouts and the need for read locks to be released before commit. The algorithm's performance is evaluated, and it is shown that the number of reads and writes are inherent to the algorithm, while the number of messages and round-trip delay times are due to the implementation using DFS. The algorithm is demonstrated to provide serial consistency, and the paper concludes that the algorithm offers many benefits not provided by previous solutions. The algorithm's approach to weighted voting has potential applications beyond replication algorithms, particularly in scenarios where decisions must be made by cooperating nodes with different probabilities of being correct.
Reach us at info@study.space