Consistency model
From Wikipedia, the free encyclopedia
In computer science, in a distributed system such as a distributed shared memory system or a distributed data store such as a database, filesystem, web caching or optimistic replication systems, there are a number of possible data consistency models. 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 to preserves memory semantics. To hold the contract, compilers may reorder some memory instructions, and library calls such as pthread_mutex_lock(), encapsulate required synchronization (Hill).
Verifying sequential consistency is undecidable in general, even for finite-state cache-coherence protocols (Qadeer).
Examples include:
- linearizability (also known as strict or atomic consistency)
- sequential consistency
- causal consistency
- release consistency
- eventual consistency
- delta consistency
- PRAM consistency
- weak consistency
- FIFO consistency
- fork consistency
- one-copy Serializability
- entry consistency
[edit] References
- Mark D. Hill Multiprocessors Should Support Simple Memory Consistency Models.
- Shaz Qadeer Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking.
[edit] Further reading
- Sarita V. Adve, Kourosh Gharachorloo (December 1996). "Shared Memory Consistency Models: A Tutorial". IEEE Computer 29 (12): 66–76.
- Kathy Yelick, Dan Bonachea, Chuck Wallace (2004). "A Proposal for a UPC Memory Consistency Model (v1.0)" (PDF).
- Mosberger, David (1993). "Memory Consistency Models". Operating Systems Review 27 (1): 18–26.
- Steinke, Robert C.; Gary J. Nutt (2004). "A unified theory of shared memory consistency". Journal of the ACM 51 (5): 800–849.
- Ali Sezgin (2004). "Formalization and verification of shared memory" (PDF). (contains many valuable references)
