Editing Consistency model (section)

== Strong consistency models ==

=== Strict consistency ===

Strict consistency is the strongest consistency model. Under this model, a write to a variable by any processor needs to be seen instantaneously by all processors.

The strict model diagram and non-strict model diagrams describe the time constraint – instantaneous. It can be better understood as though a global clock is present in which every write should be reflected in all processor caches by the end of that clock period. The next operation must happen only in the next clock period.  

In the following diagram, P means "process" and the global clock's value is represented in the Sequence column.  
{| class="wikitable"
|-
! rowspan=2 | Sequence
! colspan=2 | Strict model
! colspan=2 | Non-strict model
|-
! {{abbr|P|Processor}}1
! {{abbr|P|Processor}}2
! {{abbr|P|Processor}}1
! {{abbr|P|Processor}}2
|-
! 1
| ''W''(''x'')1
|
| ''W''(''x'')1
|
|-
! 2
|           
| ''R''(''x'')1

|
| ''R''(''x'')0
|-
! 3
|
|           
|     
| ''R''(''x'')1
|}

This is the most rigid model. In this model, the programmer's expected result will be received every time. It is deterministic. Its practical relevance is restricted to a thought experiment and formalism, because instantaneous message exchange is impossible. It doesn't help in answering the question of conflict resolution in concurrent writes to the same data item, because it assumes concurrent writes to be impossible.

=== Sequential consistency ===
{{Main|Sequential consistency}}
The [[sequential consistency]] model was proposed by Lamport (1979). It is a weaker memory model than strict consistency model.<ref name="Lamport">{{cite journal
 |  author = Lamport, Leslie
 |   title = How to make a multiprocessor computer that correctly executes multiprocess programs. 
 |    date = Sep 1979
 | journal = IEEE Transactions on Computers
 |  volume = C-28
 |   issue = 9
 |   pages = 690–691
 |     doi = 10.1109/TC.1979.1675439
| s2cid = 5679366 
 }}</ref> A write to a variable does not have to be seen instantaneously, however, writes to variables by different processors have to be seen in the same order by all processors. Sequential consistency is met if "the result of any execution is the same as if the (read and write) operations of all processes on the data store were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program."<ref name="Lamport"/><ref name="Replica"/> Adve and Gharachorloo, 1996<ref name="sharedmemory">{{cite journal
 |author1      = Sarita V. Adve
 |author2      = Kourosh Gharachorloo
 |title        = Shared Memory Consistency Models: A Tutorial
 |date         = December 1996
 |journal      = IEEE Computer
 |volume       = 29
 |issue        = 12
 |pages        = 66–76
 |url          = http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
 |access-date  = 2008-05-28
 |doi          = 10.1109/2.546611
 |citeseerx    = 10.1.1.36.8566
 |archive-date = 2008-09-07
 |archive-url  = https://web.archive.org/web/20080907125534/http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
 |url-status   = dead
}}</ref> define two requirements to implement the sequential consistency; program order and write atomicity.
* Program order: Program order guarantees that each process issues a memory request ordered by its program.
* Write atomicity: Write atomicity defines that memory requests are serviced based on the order of a single FIFO queue.

In sequential consistency, there is no notion of time or most recent write operations. There are some operations interleaving that is the same for all processes. A process can see the write operations of all processes but it can just see its own read operations. Program order within each processor and sequential ordering of operations between processors should be maintained. In order to preserve sequential order of execution between processors, all operations must appear to execute instantaneously or atomically with respect to every other processor.

These operations need only "appear" to be completed because it is physically impossible to send information instantaneously.  For instance, in a system utilizing a single globally shared bus, once a bus line is posted with information, it is guaranteed that all processors will see the information at the same instant. Thus, passing the information to the bus line completes the execution with respect to all processors and has appeared to have been executed. Cache-less architectures or cached architectures with interconnect networks that are not instantaneous can contain a slow path between processors and memories. These slow paths can result in sequential inconsistency, because some memories receive the broadcast data faster than others.

Sequential consistency can produce non-deterministic results. This is because the sequence of sequential operations between processors can be different during different runs of the program. All memory operations need to happen in the program order.

[[Linearizability]]<ref name="Linear">{{cite journal
 |   author1 = Herlihy, Maurice P.
 |   author2 = Jeannette M. Wing
 |     title = "Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems 
 |      date = July 1990
 |   journal = ACM Transactions on Programming Languages and Systems
 |    volume = 12
 |     issue = 3
 |     pages = 463–492
 |       doi = 10.1145/78969.78972
 | citeseerx = 10.1.1.142.5315
| s2cid = 228785
 }}</ref>  (also known as atomic consistency or atomic memory)<ref name="RelaxedModel"/> can be defined as sequential consistency with a real-time constraint, by considering a begin time and end time for each operation. An execution is linearizable if each operation taking place in linearizable order by placing a point between its begin time and its end time and guarantees sequential consistency.

Verifying [[sequential consistency]] through [[model checking]] is [[undecidable problem|undecidable]] in general, even for finite-state [[cache coherence]] protocols.<ref>{{cite journal
|  author = Shaz Qadeer
|   title = Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking
|    date = August 2003
| journal = IEEE Transactions on Parallel and Distributed Systems
|  volume = 14
|   issue = 8
|   pages = 730–741
|     doi = 10.1109/TPDS.2003.1225053 
|   arxiv = cs/0108016
| s2cid = 1641693
}}</ref>

=== Causal consistency ===

[[Causal consistency]]<ref name="Replica"/> defined by Hutto and Ahamad, 1990,<ref name="slow"/> is a weakening of the sequential consistency model by categorizing events into those causally related and those that are not. It defines that only write operations that are causally related, need to be seen in the same order by all processes. For example, if an event b takes effect from an earlier event a, the causal consistency guarantees that all processes see event b after event a. Tanenbaum et al., 2007 provide a stricter definition, that a data store is considered causally consistent under the following conditions:<ref name="Replica"/>

* Writes that are potentially causally related must be seen by all processes in the same order. 
* Concurrent writes may be seen in a different order on different machines.

This model relaxes sequential consistency on concurrent writes by a processor and on writes that are not causally related. Two writes can become causally related if one write to a variable is dependent on a previous write to any variable if the processor doing the second write has just read the first write. The two writes could have been done by the same processor or by different processors.

As in sequential consistency, reads do not need to reflect changes instantaneously, however, they need to reflect all changes to a variable sequentially. 
{| class="wikitable"
|-
! Sequence
! {{abbr|P|Processor}}1
! {{abbr|P|Processor}}2
! {{abbr|P|Processor}}3
! {{abbr|P|Processor}}4
|-
! 1
| W(x)1
| R(x)1
| R(x)1
| R(x)1
|-
! 2
|
| W(x)2
|
|
|-
! 3
| W(x)3
|
| R(x)3
| R(x)2
|-
! 4
|
|
| R(x)2
| R(x)3
|}

W(x)2 happens after W(x)1 due to the read made by P2 to x before W(x)2, hence this example is ''causally consistent'' under Hutto and Ahamad's definition (although not under Tanenbaum et al.'s, because W(x)2 and W(x)3 are not seen in the same order for all processes). However R(x)2 and R(x)3 happen in a different order on P3 and P4, hence this example is ''sequentially inconsistent''.<ref name=":0" />

=== Processor consistency ===

In order for consistency in data to be maintained and to attain scalable processor systems where every processor has its own memory, the [[processor consistency]] model was derived.<ref name=":0">{{Cite web|url=https://www-vs.informatik.uni-ulm.de/teach/ss05/dsm/arizona.pdf|title=Memory Consistency Models|access-date=2016-11-17|archive-date=2016-03-03|archive-url=https://web.archive.org/web/20160303220106/https://www-vs.informatik.uni-ulm.de/teach/ss05/dsm/arizona.pdf|url-status=dead}}</ref>  All processors need to be consistent in the order in which they see writes done by one processor and in the way they see writes by different processors to the same location (coherence is maintained). However, they do not need to be consistent when the writes are by different processors to different locations.

Every write operation can be divided into several sub-writes to all memories. A read from one such memory can happen before the write to this memory completes. Therefore, the data read can be stale. Thus, a processor under PC can execute a younger load when an older store needs to be stalled. Read before write, read after read and write before write ordering is still preserved in this model.

The processor consistency model<ref name="cacheconsistency">{{cite journal
 |  author = Goodman, James R
 |   title = Cache consistency and sequential consistency
 |    date = 1991
 | journal = IEEE Scalable Coherent Interface (SCI) Working Group
}}</ref> is similar to the [[PRAM consistency]] model with a stronger condition that defines all writes to the same memory location must be seen in the same sequential order by all other processes. Processor consistency is weaker than sequential consistency but stronger than the PRAM consistency model.

The [[Stanford DASH|Stanford DASH multiprocessor system]] implements a variation of processor consistency which is incomparable (neither weaker nor stronger) to Goodman's definitions.<ref name="senftleben13" /> All processors need to be consistent in the order in which they see writes by one processor and in the way they see writes by different processors to the same location. However, they do not need to be consistent when the writes are by different processors to different locations.

=== Pipelined RAM consistency, or FIFO consistency ===

[[PRAM consistency|Pipelined RAM consistency]] (PRAM consistency) was presented by Lipton and Sandberg in 1988<ref name="pram_lipton">{{cite tech report|first=R.J.|last=Lipton|author2=J.S. Sandberg.|title=PRAM: A scalable shared memory|number=CS-TR-180-88|institution=Princeton University|year=1988}}</ref>  as one of the first described consistency models. Due to its informal definition, there are in fact at least two subtly different implementations,<ref name="senftleben13">{{cite thesis|degree=M.Sc.|last=Senftleben|first=Maximilian|date=2013|title=Operational Characterization of Weak Memory Consistency Models|publisher=University of Kaiserslautern|url=https://es.cs.uni-kl.de/publications/datarsg/Senf13.pdf}}</ref> one by Ahamad et al. and one by Mosberger.

In PRAM consistency, all processes view the operations of a single process in the same order that they were issued by that process, while operations issued by different processes can be viewed in different order from different processes. PRAM consistency is weaker than processor consistency. PRAM relaxes the need to maintain coherence to a location across all its processors. Here, reads to any variable can be executed before writes in a processor. Read before write, read after read and write before write ordering is still preserved in this model.  
{| class="wikitable"
|-
! Sequence
! {{abbr|P|Processor}}1
! {{abbr|P|Processor}}2
! {{abbr|P|Processor}}3
! {{abbr|P|Processor}}4
|-
! 1 
| W(x)1
|
|
|
|-
! 2
|
| R(x)1
|
|
|-
! 3
|
| W(x)2
|
|
|-
! 4
|
|
| R(x)1
| R(x)2
|-
! 5
|
|
| R(x)2
| R(x)1
|}

=== Cache consistency ===
Cache consistency<ref name="cacheconsistency"/><ref name="unified"/> requires that all write operations to the same memory location are performed in some sequential order. Cache consistency is weaker than processor consistency and incomparable with PRAM consistency.

=== Slow consistency ===
[[File:Slow memory.gif|thumb|Slow memory]]

In slow consistency,<ref name="unified"/> if a process reads a value previously written to a memory location, it cannot subsequently read any earlier value from that location. Writes performed by a process are immediately visible to that process. Slow consistency is a weaker model than PRAM and cache consistency.

'''Example:'''
Slow memory diagram depicts a slow consistency example. The first process writes 1 to the memory location X and then it writes 1 to the memory location Y. The second process reads 1 from Y and it then reads 0 from X even though X was written before Y.

Hutto, Phillip W., and Mustaque Ahamad (1990)<ref name="slow">{{cite book
|author1=Hutto, Phillip W. |author2=Mustaque Ahamad
|title=Proceedings.,10th International Conference on Distributed Computing Systems
|chapter=Slow memory: Weakening consistency to enhance concurrency in distributed shared memories
|    date = 1990
| publisher = IEEE 
|   pages = 302–309
|     doi = 10.1109/ICDCS.1990.89297
|    isbn = 978-0-8186-2048-5
|s2cid=798676
}}</ref> illustrate that by appropriate programming, slow memory (consistency) can be expressive and efficient. They mention that slow memory has two valuable properties; locality and supporting reduction from atomic memory. They propose two algorithms to present the expressiveness of slow memory.