Editing Consistency model (section)

== Weak memory consistency models ==

The following models require specific synchronization by programmers.

=== Weak ordering ===

Weak ordering classifies memory operations into two categories: ''data operations'' and ''synchronization operations''. To enforce program order, a programmer needs to find at least one synchronisation operation in a program. Synchronization operations signal the processor to make sure it has completed and seen all previous operations done by all processors. Program order and atomicity is maintained only on synchronisation operations and not on all reads and writes. This was derived from the understanding that certain memory operations – such as those conducted in a critical section - need not be seen by all processors until after all operations in the critical section are completed. It assumes reordering memory operations to data regions between synchronisation operations does not affect the outcome of the program. This exploits the fact that programs written to be executed on a multi-processor system contain the required synchronization to make sure that data races do not occur and SC outcomes are produced always.<ref>{{Cite web|url=http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf|title=Shared Memory Consistency Models : A tutorial|access-date=2008-05-28|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>
{| class="wikitable"
|-
! {{abbr|P|Processor}}1
! {{abbr|P|Processor}}2
|- style="vertical-align:top;"
| {{pre|1=
X = 1;
''fence''
 
xready = 1;
}}
| {{pre|1=
''fence''
while (!xready) {}; 
 
''fence''
 
y = 2;
}}
|}

Coherence is not relaxed in this model. Once these requirements are met, all other "data" operations can be reordered. The way this works is that a counter tracks the number of data operations and until this counter becomes zero, the synchronisation operation isn't issued. Furthermore, no more data operations are issued unless all the previous synchronisations are completed. Memory operations in between two synchronisation variables can be overlapped and reordered without affecting the correctness of the program. This model ensures that write atomicity is always maintained, therefore no additional safety net is required for weak ordering.

In order to maintain weak ordering, write operations prior to a synchronization operation must be globally performed before the synchronization operation. Operations present after a synchronization operation should also be performed only after the synchronization operation completes. Therefore, accesses to synchronization variables is sequentially consistent and any read or write should be performed only after previous synchronization operations have completed.

There is high reliance on explicit synchronization in the program. For weak ordering models, the programmer must use atomic locking instructions such as test-and-set, fetch-and-op, store conditional, load linked or must label synchronization variables or use fences.

===Release consistency===
The [[release consistency]] model relaxes the weak consistency model by distinguishing the entrance synchronization operation from the exit synchronization operation. Under weak ordering, when a synchronization operation is to be seen, all operations in all processors need to be visible before the synchronization operation is done and the processor proceeds. However, under the release consistency model, during the entry to a critical section, termed as "acquire", all operations with respect to the local memory variables need to be completed. During the exit, termed as "release", all changes made by the local processor should be propagated to all other processors. Coherence is still maintained.

The acquire operation is a load/read that is performed to access the critical section. A release operation is a store/write performed to allow other processors to use the shared variables.

Among synchronization variables, sequential consistency or processor consistency can be maintained. Using SC, all competing synchronization variables should be processed in order. However, with PC, a pair of competing variables need to only follow this order. Younger acquires can be allowed to happen before older releases.{{cn|date=December 2023}}

==== RCsc and RCpc ====

There are two types of release consistency, release consistency with sequential consistency (RCsc) and  release consistency with processor consistency (RCpc). The latter type denotes which type of consistency is applied to those operations nominated below as special.

There are special (cf. ordinary) memory operations, themselves consisting of two classes of operations: ''sync'' or ''nsync'' operations. The latter are operations not used for synchronisation; the former are, and consist of ''acquire'' and ''release'' operations. An acquire is effectively a read memory operation used to obtain access to a certain set of shared locations. Release, on the other hand, is a write operation that is performed for granting permission to access the shared locations.

For sequential consistency (RCsc), the constraints are:
* acquire → all,
* all → release,
* special → special.

For processor consistency (RCpc) the write to read program order is relaxed, having constraints:
* acquire → all,
* all → release,
* special → special (except when special write is followed by special read).

Note: the above notation A → B, implies that if the operation A precedes B in the program order, then program order is enforced.

===Entry consistency ===
This is a variant of the release consistency model. It also requires the use of ''acquire'' and ''release'' instructions to explicitly state an entry or exit to a critical section. However, under entry consistency, every shared variable is assigned a synchronization variable specific to it. This way, only when the acquire is to variable x, all operations related to x need to be completed with respect to that processor. This allows concurrent operations of different critical sections of different shared variables to occur. Concurrency cannot be seen for critical operations on the same shared variable. Such a consistency model will be useful when different matrix elements can be processed at the same time.

=== Local consistency ===

In local consistency,<ref name="unified"/> each process performs its own operations in the order defined by its program. There is no constraint on the ordering in which the write operations of other processes appear to be performed. Local consistency is the weakest consistency model in shared memory systems.

=== General consistency ===

In general consistency,<ref>{{cite journal
| author1 = Singhal, Mukesh
| author2 = Niranjan G. Shivaratri
|   title = Advanced concepts in operating systems. 
| url = https://archive.org/details/advancedconcepts0000sing
| url-access = registration
| journal = McGraw-Hill, Inc
|    date = 1994
}}</ref> all the copies of a memory location are eventually identical after all processes' writes are completed.

=== Eventual consistency ===

An [[eventual consistency]]<ref name="Replica"/> is a weak consistency model in a system with the lack of simultaneous updates. It defines that if no update takes a very long time, all replicas eventually become consistent.

Most shared decentralized databases have an eventual consistency model, either BASE: basically available; soft state; eventually consistent, or a combination of [[ACID (computer science)|ACID]] and BASE sometimes called SALT: sequential; agreed; ledgered; tamper-resistant, and also symmetric; admin-free; ledgered; and time-consensual.<ref>Collin Cusce.
[https://medium.com/@collin.cusce/blockchain-salt-a-descriptive-model-b19c973fef5f "SALT: A Descriptive Model For Blockchain"] {{Webarchive|url=https://web.archive.org/web/20200803201126/https://medium.com/@collin.cusce/blockchain-salt-a-descriptive-model-b19c973fef5f |date=2020-08-03 }}.
2018.</ref><ref>
Stefan Tai, Jacob Eberhardt, and Markus Klems.
[http://www.ise.tu-berlin.de/fileadmin/fg308/publications/2017/2017-tai-eberhardt-klems-SALT.pdf "Not ACID, not BASE, but SALT: A Transaction Processing Perspective on Blockchains"].
2017.
</ref><ref>
Chao Xie, Chunzhi Su, Manos Kapritsos, Yang Wang,
Navid Yaghmazadeh, Lorenzo Alvisi, Prince Mahajan.
[https://web.archive.org/web/20181019205538/https://pdfs.semanticscholar.org/d2ed/d36bc2ce58f26132980b5d609716d084c7b4.pdf "Salt: Combining ACID and BASE in a Distributed Database"].
</ref>