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.[1]
Verifying sequential consistency is undecidable in general, even for finite-state cache-coherence protocols.[2]
Examples include:
- linearizability (also known as strict or atomic consistency)
- sequential consistency
- causal consistency
- release consistency
- eventual consistency
- delta consistency
- PRAM consistency (also known as FIFO consistency)
- weak consistency
- vector-field consistency
- fork consistency
- one-copy Serializability
- entry consistency
References
- ^ Mark D. Hill (August 1998). "Multiprocessors Should Support Simple Memory Consistency Models". IEEE Computer 31 (8): pp.28–34. doi:.
- ^ Shaz Qadeer (August 2003). "Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking". IEEE Transactions on Parallel and Distributed Systems 14 (8): pp.730–741. doi:.
Further reading
- Sarita V. Adve, Kourosh Gharachorloo (December 1996). "Shared Memory Consistency Models: A Tutorial". IEEE Computer 29 (12): 66–76. http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf. Retrieved 2008-05-28.
- Kathy Yelick, Dan Bonachea, Chuck Wallace (2004) (PDF). A Proposal for a UPC Memory Consistency Model (v1.0). http://www.gwu.edu/~upc/downloads/upcmem.pdf.
- Mosberger, David (1993). "Memory Consistency Models". Operating Systems Review 27 (1): 18–26. doi:. http://citeseer.ist.psu.edu/mosberger93memory.html.
- Steinke, Robert C.; Gary J. Nutt (2004). "A unified theory of shared memory consistency". Journal of the ACM 51 (5): 800–849. doi:. http://arxiv.org/abs/cs.DC/0208027.
- Ali Sezgin (2004) (PDF). Formalization and verification of shared memory. http://www.atilim.edu.tr/~asezgin/diss_finalcopy.pdf. (contains many valuable references)
External links
- Consistency Models
- IETF slides
- Memory Ordering in Modern Microprocessors, Part I and Part II, by Paul E. McKenney (2005). Linux Journal
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
