Atomic semantics
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (January 2013) |
Atomic semantics is a term which describes the guarantees provided by a data register shared by several processors in a parallel machine or in a network of computers working together.
The read and write registers are one of the important and basic objects encountered in distributed theory systems. Atomic semantics are very strong. An atomic register provides strong guarantees even when there is concurrency and failures.A register R could be accessed by two base operations: R.Read ,and R.write(v).The R.Read will return the value of R and R.write(v) writes a new value into R. A register is called atomic semantic if it satisfies the two following properties: 1)Each invocation operation of a read or write operation :
- Should become visible just as if it was executed already at an only one point τ(op)
- τ (op) works as follow:
τb(op) ≤ τ (op) ≤ τe(op): where τb(op) and τe(op) indicate the time where exactly the operation op started and finished.
- If op1 = op2) ⇒τ (op1)≠τ (op2)
2) Every read operation returns the value written by the closest write which came before write invocation in the sequence by the τ () associated with the operation invocations .It means that an atomic register is defined where all its operation invocations have been executed sequentially.
An atomic register is one that is linearizable to a sequential safe register.As it shown in the picture.
An atomic register could be defined for a variable with a single writer but multiple readers(SWMR) or single-writer/multi-reader (SWMR), 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.Therfore, 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.
Since the R.write(3) and R.write(2) are concurrent with each other,they could appear to an external observer if R.write(2) was executed before R.write(3).
In that case, if the last two read invocations return the value 3, the execution would be correct;For example,the observer should see the following execution: R.write(1), R.read()→1, R.write(2), R.write(3), R.read()→3, R.read()→3. Since the second read invocation by p1 is concurrent with R.Write(2) and R.Write(3) ,so the second read invocation by p1 could appear as having been executed before these two write operations and it should return the value 1 in order for the register to behave as an atomic register.
See also
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).