Consistency model
Encyclopedia
In computer science
, consistency models are used in distributed systems
like distributed shared memory
systems or distributed data stores (such as a filesystems, database
s, optimistic replication
systems or Web caching). The system supports a given model, if operations on memory follow specific rules. The data consistency model specifies a contract between programmer and system, wherein the system guarantees that if the programmer follows the rules, memory will be consistent and the results of memory operations will be predictable.
High level languages, such as C, C++, and Java, partially maintain the contract by translating memory operations into low-level operations in a way that preserves memory semantics. To hold to the contract, compilers may reorder some memory instructions, and library calls such as
Verifying sequential consistency is undecidable
in general, even for finite-state cache-coherence protocols.
Consistency models define rules for the apparent order and visibility of updates, and it is a continuum
with tradeoffs.
The consistency model has to determine whether client B does see the write from client A or not.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, consistency models are used in distributed systems
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
like distributed shared memory
Distributed shared memory
Distributed Shared Memory , in Computer Architecture is a form of memory architecture where the memories can be addressed as one address space...
systems or distributed data stores (such as a filesystems, database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
s, optimistic replication
Optimistic replication
Optimistic replication is a strategy for replication in which replicas are allowed to diverge.Traditional pessimistic replication systems try to guarantee from the beginning that all of the replicas are identical to each other, as if there was only a single copy of the data all along...
systems or Web caching). The system supports a given model, if operations on memory follow specific rules. The data consistency model specifies a contract between programmer and system, wherein the system guarantees that if the programmer follows the rules, memory will be consistent and the results of memory operations will be predictable.
High level languages, such as C, C++, and Java, partially maintain the contract by translating memory operations into low-level operations in a way that preserves memory semantics. To hold to the contract, compilers may reorder some memory instructions, and library calls such as
pthread_mutex_lock encapsulate required synchronization.Verifying sequential consistency is undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
in general, even for finite-state cache-coherence protocols.
Consistency models define rules for the apparent order and visibility of updates, and it is a continuum
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
with tradeoffs.
Example
Assume that the following case occurs:- The row X is replicated on nodes M and N
- The client A writes row X to node N
- After a period of time t, client B reads row X from node M
The consistency model has to determine whether client B does see the write from client A or not.
Types
A non-exhaustive list of consistency models are- causal consistencyCausal consistencyCausal consistency is one of the consistency models used in the domain of the concurrent programming ....
- delta consistencyDelta consistencyDelta consistency is one of the consistency models used in the domain of parallel programming, for example in distributed shared memory, distributed transactions, and Optimistic replication...
- entry consistency
- eventual consistencyEventual consistencyEventual consistency is one of the consistency models used in the domain of parallel programming, for example in distributed shared memory, distributed transactions, and optimistic replication, it means that given a sufficiently long period of time over which no changes are sent, all updates can be...
- fork consistency
- linearizabilityLinearizabilityIn concurrent programming, an operation is atomic, linearizable, indivisible or uninterruptible if it appears to the rest of the system to occur instantaneously. Atomicity is a guarantee of isolation from concurrent processes...
(also known as strict or atomic consistency) - one-copy serializability
- PRAM consistencyPRAM consistencyPRAM consistency also known as FIFO consistency, or Processor consistency.All processes see memory writes from one process in the order they were issued from the process....
(also known as FIFO consistency) - release consistencyRelease consistencyRelease consistency is one of the consistency models used in the domain of the concurrent programming ....
- sequential consistencySequential consistencySequential consistency is one of the consistency models used in the domain of concurrent programming . It was first defined as the property that requires that ".....
- serializabilitySerializabilityIn concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...
- vector-field consistencyVector-field consistencyVector-Field ConsistencyDesignation coined by L. Veiga. is a consistency model for replicated data , initially described in a paper which was awarded the best-paper prize in the ACM/IFIP/Usenix Middleware Conference 2007...
- weak consistencyWeak consistencyThe name weak consistency may be used in two senses. In the first sense, strict and more popular, the weak consistency is one of the consistency models used in the domain of the concurrent programming The name weak consistency may be used in two senses. In the first sense, strict and more popular,...
External links
- Consistency Models
- IETF slides
- Memory Ordering in Modern Microprocessors, Part I and Part II, by Paul E. McKenney (2005). Linux JournalLinux JournalLinux Journal is a monthly technology magazine published by Belltown Media, Inc. of Houston, Texas. The magazine focuses specifically on Linux, allowing the content to be a highly specialized source of information for open source enthusiasts.-History:...