Atomic semantics

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 if it satisfies the two following properties:

1) Each invocation operation(op) of a read or write operation :

• Must appears just as if it was executed already 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 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 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.Atomic registers are linearizable.

Atomic/Linearizable register:

Termination: when a node is correct,sooner or later each read and write operation will complete.

Safety Property(Lineariztion 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.

atomic

The following picture shows where we should put the linearization point for each operation:

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.

Atomic MWMR1


See also[edit]

References[edit]

  • 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).