Regular semantics

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 consistent with real-time and that read operations return either the value of the last write completed before the read begins, or that of one of the writes which are concurrent with the read.

[1] A single-writer multi-reader (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 getting into the proof, first, it should be understood what the new/old inversion means.

So, the only required proof is to show that a regular register with no new/old inversion is atomic.

Furthermore, this total order is an execution of M only adds an order on operations that are overlapping in M. If there is no overlapping between a read and write operations, there is no difference between the regularity and atomicity.

Finally, it can be stated that S is legal since each read operation gets the last written value that comes before it in the total order.