World Library  
Flag as Inappropriate
Email this Article

Quorum (distributed computing)

Article Id: WHEBN0022254482
Reproduction Date:

Title: Quorum (distributed computing)  
Author: World Heritage Encyclopedia
Language: English
Subject: Apache Cassandra, Transaction processing, IT
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Quorum (distributed computing)

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. 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 control method[1] , as well as a commit method to ensure transaction atomicity in the presence of network partitioning.[1]

Quorum-based voting in commit protocols

In a distributed database system, a transaction could be executing 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 Vi. Let us assume that the total number of votes in the system is V and the abort and commit quorums are Va and Vc, respectively. Then the following rules must be obeyed in the implementation of the commit protocol:

  1. Va + Vc > V, where 0 < Vc, Va \le V.
  2. Before a transaction commits, it must obtain a commit quorum Vc.
    The total of at least one site that is prepared to commit and zero or more sites waiting \ge Vc.[2]
  3. Before a transaction aborts, it must obtain an abort quorum Va
    The total of zero or more sites that are prepared to abort or any sites waiting \ge Va.

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, 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 [Gifford, 1979][3] . Each copy of a replicated data item is assigned a vote. Each operation then has to obtain a read quorum (Vr) or a write quorum (Vw) 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:

  1. Vr + Vw > V
  2. Vw > V/2

The first rule ensures that a data item is not read and written by two transactions concurrently. 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

References

  1. ^ a b Ozsu, Tamer M; Valduriez, Patrick (1991). "12". Principles of distributed database systems (2nd ed.). Upper Saddle River, NJ: Prentice-Hall, Inc.  
  2. ^ Skeen, Dale. "A Quorum-based Commit Protocol". Cornell University ECommons Library. Retrieved 10 February 2013. 
  3. ^ Gifford, David K. (1979). "SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principles". Pacific Grove, California, United States: ACM. pp. 150–162.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.