A quorum is the minimum number of votes that a distributed transaction has to obtain in order to be allowed to perform an operation in a
distributed system
Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers.
The components of a distributed system commun ...
. A quorum-based technique is implemented to enforce consistent operation in a distributed system.
Quorum-based techniques in distributed database systems
Quorum-based voting can be used as a
replica
A replica is an exact (usually 1:1 in scale) copy or remake of an object, made out of the same raw materials, whether a molecule, a work of art, or a commercial product. The term is also used for copies that closely resemble the original, without ...
control method,
[
]
as well as a commit method to ensure
transaction atomicity in the presence of
network partitioning
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
.
Quorum-based voting in commit protocols
In a distributed database system, a transaction could execute its operations at multiple sites. Since atomicity requires every distributed transaction to be atomic, the transaction must have the same fate (
commit or
abort) at every site. In case of network partitioning, sites are partitioned and the partitions may not be able to communicate with each other. This is where a quorum-based technique comes in. The fundamental idea is that a transaction is executed if the majority of sites vote to execute it.
Every site in the system is assigned a vote V
i. Let us assume that the total number of votes in the system is V and the abort and commit quorums are V
a and V
c, respectively. Then the following rules must be obeyed in the implementation of the commit protocol:
# V
a + V
c > V, where 0 < V
c, V
a V.
# Before a transaction commits, it must obtain a commit quorum V
c.
The total of at least one site that is prepared to commit and zero or more sites waiting
V
c.
# Before a transaction aborts, it must obtain an abort quorum V
aThe total of zero or more sites that are prepared to abort or any sites waiting
V
a.
The first rule ensures that a transaction cannot be committed and aborted at the same time. The next two rules indicate the votes that a transaction has to obtain before it can terminate one way or the other.
Quorum-based voting for replica control
In replicated databases, a data object has copies present at several sites. To ensure
serializability
In the fields of databases and transaction processing (transaction management), a schedule (or history) of a system is an abstract model to describe the order of executions in a set of transactions running in the system. Often it is a ''list'' o ...
, no two transactions should be allowed to read or write a data item concurrently. In case of replicated databases, a quorum-based replica control protocol can be used to ensure that no two copies of a data item are read or written by two transactions concurrently.
The quorum-based voting for replica control is due to
ifford, 1979[
{{Cite conference
, first = David K.
, last = Gifford
, title = Weighted voting for replicated data
, conference = SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principles
, year = 1979
, pages = 150–162
, place = Pacific Grove, California, United States
, publisher = ACM
, doi = 10.1145/800215.806583
, citeseerx= 10.1.1.12.6256
]
Each copy of a replicated data item is assigned a vote. Each operation then has to obtain a ''read quorum'' (V
r) or a ''write quorum'' (V
w) to read or write a data item, respectively. If a given data item has a total of V votes, the quorums have to obey the following rules:
# V
r + V
w > V
# V
w > V/2
The first rule ensures that a data item is not read and written by two transactions concurrently. Additionally, it ensures that a read quorum contains at least one site with the newest version of the data item. The second rule ensures that two write operations from two transactions cannot occur concurrently on the same data item. The two rules ensure that one-copy serializability is maintained.
See also
*
CAP theorem
In database theory, the CAP theorem, also named Brewer's theorem after computer scientist Eric Brewer (scientist), Eric Brewer, states that any distributed data store can provide at most Inconsistent triad, two of the following three guarantees:
; ...
*
Database transaction
A database transaction symbolizes a unit of work, performed within a database management system (or similar system) against a database, that is treated in a coherent and reliable way independent of other transactions. A transaction generally rep ...
*
Replication (computer science)
Replication in computing refers to maintaining multiple copies of data, processes, or resources to ensure consistency across redundant components. This fundamental technique spans database management system, databases, file system, file systems, a ...
*
Atomicity (database systems)
In database systems, atomicity (; from ) is one of the ACID (''Atomicity, Consistency, Isolation, Durability'') transaction properties. An atomic transaction is an ''indivisible'' and '' irreducible'' series of database operations such that eit ...
References
Database management systems
Transaction processing