Hierarchical quorum consensus: a new algorithm for managing replicated data
IEEE Transactions on ComputersPublished 1 January 1991
Akhil Kumar
Citations210
SJR quartileQ1
SJR score1.16
SNIP1.61
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that, given a collection of n copies of an object, the method allows a quorum to be formed with n/sup 0.63/ copies versus ((n+1)/2) copies in the case of the majority voting algorithm.
Abstract
A novel algorithm for managing replicated data is presented. The proposed method is based on organizing the copies of an object into a logical, multilevel hierarchy, and extending the quorum consensus algorithm to such an environment. Several properties of the method are derived and optimality conditions are given for minimizing the quorum size. It is shown that, given a collection of n copies of an object, the method allows a quorum to be formed with n/sup 0.63/ copies versus ((n+1)/2) copies in the case of the majority voting algorithm. Tradeoffs between the proposed method and three other quorum-based methods are discussed, and the main features of each method are highlighted.>
Keywords
Computer Science
Weighted voting for replicated data
1,323 Citations1979David K. Gifford
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.
ACM Transactions on Database SystemsA Majority consensus approach to concurrency control for multiple copy databases
1,006 Citations1979Robert Thomas
A “majority consensus” algorithm which represents a new solution to the update synchronization problem for multiple copy databases is presented and can function effectively in the presence of communication and database site outages.
ACM Transactions on Computer SystemsA √N algorithm for mutual exclusion in decentralized systems
736 Citations1985Mamoru Maekawa
An algorithm is presented that uses only only c√N messages to create mutual exclusion in a computernetwork, where N is the number of nodes and c is a constant between 3 and 5.
Journal of the ACMHow to assign votes in a distributed system
563 Citations1985Héctor García-Molina, Daniel Barbará
In this paper, both of these strategies for achieving mutual exclusion of groups of nodes without communication are studied in detail and it is shown that they are not equivalent in general (although they are in some cases) and a number of other interesting properties are proved.
An efficient, fault-tolerant protocol for replicated data management
225 Citations1985Amr El Abbadi, Dale Skeen +1 more
A data management protocol for executing transactions on a replicated database that ensures one-copy serializability and tolerates a large class of failures, including: processor and communication link crashes, partitioning of the communication network, lost messages, and slow responses of processors and communication links.
International Conference on Distributed Computing SystemsVoting with Witnesses: A Constistency Scheme for Replicated Files.
161 Citations1986J.-F. Paris
It is shown, that under very general assumptions, the reliability of a replicated file consisting of n copies and m witnesses is the same as the reliabilityof a replicatedfile consisting ofn + m copies.
Dynamic voting
134 Citations1987Sushil Jajodia, David Mutchler
This paper proposes an extension of this scheme which permits a file to be updated in a partition provided it contains a majority of up-to-date copies and develops a stochastic model which gives insight into the improvements afforded by the scheme over the voting scheme.
ACM Transactions on Database SystemsDynamic quorum adjustment for partitioned data
134 Citations1987Maurice Herlihy
This paper introduces a new method for managing replicated data objects in the presence of partitions that supports a wider range of quorums and systematically exploits the semantics of typed objects to support more flexible quorum adjustment.
ACM SIGOPS Operating Systems ReviewConsistency and recovery control for replicated files
123 Citations1985Danco Davčev, Walter A. Burkhard
A consistency and recovery control scheme for replicated files to improve the availability of a logical file in the presence of site failures and network partitions.
ACM Transactions on Database SystemsAchieving robustness in distributed database systems
123 Citations1983Derek L. Eager, Kenneth C. Sevcik
A level of robustness termed maximal partial operability is identified, which is the highest level attainable without significantly degrading performance under models of concurrency control and robustness.
IEEE Transactions on Software EngineeringPerformance characterization of quorum-consensus algorithms for replicated data
100 Citations1989Mustaque Ahamad, Mostafa Ammar
The authors develop a model and define performance measures for a replicated data system that makes use of a quorum-consensus algorithm to maintain consistency and derive optimal read and write quorums which maximize the proportion of successful transactions.
Efficient dynamic voting algorithms
91 Citations2003J.-F. Paris, Darrell D. E. Long
Optimistic dynamic voting is found to perform as well as the best existing voting algorithms while topological dynamic voting performs much better than all other voting algorithms when two or more copies reside in the same nonpartitionable group.
Efficient solution to the distributed mutual exclusion problem
84 Citations1989Divyakant Agrawal, Amr El Abbadi
This work presents an efficient fault-tolerant solution to the distributed mutual exclusion problem that requires logn messages in the best case and is resilient to both site and communication failures, even when such failures lead to network partitions.
Consistency and recovery control for replicated files
72 Citations1985Danco Davčev, Walter A. Burkhard
Protocols for dynamic vote reassignment
32 Citations1986Daniel Barbará, Héctor García-Molina +1 more
Protocols are given which allow nodes to select new vote values autonomously while still main ta in ing mutua l exclus ion r e q u i r e m e n t s .
Multidimensional voting: a general method for implementing synchronization in distributed systems
22 Citations2002S.Y. Cheung, Mustaque Ahamad +1 more
It is shown how multidimensional voting can be used to easily implement novel algorithms for synchronizing access to replicated data or to ensure mutual exclusion.
Optimizing vote and quorum assignments for reading and writing replicated data
12 Citations2003S.Y. Cheung, Mustaque Ahamad +1 more
An enumeration algorithm is presented that can be used to find the vote and quorum assignments that need to be considered for achieving optimal availability in a system where node availabilities can be different and the mix of the read and write operations is arbitrary.
Lecture notes in computer scienceOptimizing voting-type algorithms for replicated data
10 Citations1988Akhil Kumar, Arie Segev
It is argued that an optimal vote assignment is one which meets given resiliency goals and yet incurs the least communications cost compared with all other alternative assignments.