Regular semantics

Regular semantics(Regular register) is a computing 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. Regular semantics are defined for a variable with a single writer but multiple readers. These semantics are stronger than safe semantics but weaker than atomic semantics: they guarantee that there is a total order to the write operations which is consistent with real-time and that read operations return either the value of the last completed write or that of one of the writes which are concurrent with the read.

Regular semantics are defined for a variable with a single writer but multiple readers(SWMR).An SWMR regular register is an SWMR safe register if it satisfies the following property:

A read operation which is concurrent with one or many write operations can return either the old initial value of the register or a new value written by any of the write operations.

Safe Register

Regular register is weaker than linearizability. In the above example,according to the regular register's definition,the third read should return 3 since the read operation does not concurrent with any write operation.On the other hand,the second read may return 2 or 3, and the first read will return either 5 or 2.By and large,the first read could return 3 and the second read could return 2.This behavior is definitely not linearizable.Therfore,we can state that the regular semantic is a weaker property than a linearizable register.On the other hand,Lamport proved that a linearziable register may be implemented from a safe semantics.Based on the definition we provided above,we can conclude that a linearizable register is the strongest register which could be implemented from safe semantics.

A Theorem from Regularity to Atomicity: An SWMR atomic semantics is an SWMR regular register if any of its execution history H satisfies the following property: r1 and r2 are any two read invocations: (r1 →H r2) ⇒ ¬π(r2) →H π(r1)

Before we get into the proof,first we should know what does the new/old inversion mean.As it shown in the picture below,by looking at the execution we can see that the only difference between a regular execution and an atomic execution is when a = 0 and b = 1.In this execution,when we consider the two read invocations R.read() → a followed by R.read() → b, our first value(new value) is a = 0 while the second value(old value) is b=1.This is actually the main difference between atomacity and regularity.

figure1

The theorem above states that a Single writer multi-reader regular register without new or old inversion is an atomic register.By looking at the picture we can say that as R.read() → a →H R.read() → b and R.write(1) →H R.write(0), it is not possible to have π (R.read() → b) =R.write(1) and π (R.read() → a) = R.write(0) if the execution is atomic. For proving the theorem above,first we should prove that the register is safe,next we should show that the register is regular,and then at the end we should show that the register does not allow for new/old inversion which proves the atomicity. By the definition of the atomic register we know that a Single writer multiple reader atomic register is regular and satisfies the no new/old inversion property.So,we only need to show that a regular register with no new/old inversion is atomic.

We know that for any two read invocations (r1 and r2) when the register is regular and there is no new/old inversion (r1 →H r2) ⇒sn(π(r1)) ≤ sn(π(r2))�.For any execution(M)there is a total order (s)which includes the same operation invocations .

• Atomic semantics
• Safe semantics

References

• Lamport, Leslie "On Interprocess Communication" http://research.microsoft.com/en-us/um/people/lamport/pubs/interprocess.pdf (1986)