Editing Consistency model (section)

=== 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>