Atomic semantics
title: "Atomic semantics" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["concurrency-control"] topic_path: "general/concurrency-control" source: "https://en.wikipedia.org/wiki/Atomic_semantics" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
Atomic semantics is a type of guarantee provided by a data register shared by several processors in a parallel machine or in a network of computers working together. Atomic semantics are very strong. An atomic register provides strong guarantees even when there is concurrency and failures.
A read/write register R stores a value and is accessed by two basic operations: read and write(v). A read returns the value stored in R and write(v) changes the value stored in R to v. A register is called atomic if it satisfies the two following properties:
- Each invocation op of a read or write operation:
•Must appear as if it were executed at a single point τ(op) in time.
•τ (op) works as follow: τb(op) ≤ τ (op) ≤ τe(op): where τb(op) and τe(op) indicate the time when the operation op begins and ends.
•If op1 ≠ op2, then τ (op1)≠τ (op2)
- Each read operation returns the value written by the last write operation before the read, in the sequence where all operations are ordered by their τ values.
Atomic/Linearizable register:
Termination: when a node is correct, sooner or later each read and write operation will complete.
Safety Property (Linearization points for read and write and failed operations):
Read operation:It appears as if happened at all nodes at some times between the invocation and response time.
Write operation: Similar to read operation, it appears as if happened at all nodes at some times between the invocation and response time.
Failed operation(The atomic term comes from this notion):It appears as if it is completed at every single node or it never happened at any node.
Example : We know that an atomic register is one that is linearizable to a sequential safe register.
::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/e8/Atomic_register1.jpg" caption="atomic"] ::
The following picture shows where we should put the linearization point for each operation:
::figure[src="https://upload.wikimedia.org/wikipedia/commons/b/bd/Atomic_register.jpg" caption="Atomic register"] ::
An atomic register could be defined for a variable with a single writer but multi- readers (SWMR), single-writer/single-reader (SWSR), or multi-writer/multi-reader (MWMR). Here is an example of a multi-reader multi-writer atomic register which is accessed by three processes (P1, P2, P3). Note that R. read() → v means that the corresponding read operation returns v, which is the value of the register. Therefore, the following execution of the register R could satisfies the definition of the atomic registers: R.write(1), R.read()→1, R.write(3), R.write(2), R.read()→2, R.read()→2.
::figure[src="https://upload.wikimedia.org/wikipedia/commons/0/04/Atomic_MWMR1.jpg" caption="Atomic MWMR1"] ::
References
- Atomic semantics are defined formally in Lamport's "On Interprocess Communication" Distributed Computing 1, 2 (1986), 77–101. (Also appeared as SRC Research Report 8).
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::