Converting Lamport's regular register to atomic register (Q1114404)

The problem dealt with in the paper is that of constructing atomic multi- valued n-reader 1-writer registers from atomic Boolean n-reader 1-writer registers. A register is an abstraction of an asynchronous interface communication with senders (writers) and receivers (readers) and the state of the communication medium represented by the value of the register. Asynchronous communication implies that some operations may overlap. In the 1-writer case there cannot be overlapping of writers but a read may overlap a write. Now it is easy to implement in hardware Boolean 1-writer 1-reader registers which are safe (i.e., such that a read that does not overlap a write returns the most recently written value, but if it overlaps a write it may return any value from the domain of the register). One usually wants to construct a regular multi-valued register (i.e., a safe register in which a read that overlaps a write obtains either the old or the new value). The present paper takes the lead from a construction by Lamport which gives regular multi-valued registers from regular Boolean ones but it does not imply atomicity even though the Boolean registers are atomic (where atomic means that reads and writes behave as if they occur in some total order, such that a read obtains the value of the most recent ``essentially complete'' write and of two successive reads the first cannot obtain a newer value than the second). The main result of the paper is a construction which improves Lamport's one to insure atomicity.