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. We can state that S is built as follow: we start from the total order on the write operations and we will insert the read operation as follow: first: Read operation (r) is inserted after the associated write operation (π(r)). Second: If two read operations (r1,r2) have the same (sn(r1)=sn(r2)) then first insert the operation which starts first in the execution. S includes all the operation invocation of M, from which it follows that S and M are equivalent. Since all the operations are ordered based on their sequence numbers is slightly a total order. 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, we can state that S is legal since each read operation gets the last written value that comes before it in the total order. Therefore, the corresponding history is linearizable. Since this reasoning does not rely on a particular history H, it implies that the register is atomic. Since atomicity (linearizability) is a local property, we can state that a set of SWMR regular registers behave atomically as soon as each of them satisfies the no new/old inversion property. Atomic semantics Safe semantics References Lamport, Leslie "On Interprocess Communication" http://research.microsoft.com/en-us/um/people/lamport/pubs/interprocess.pdf (1986)