The problem of atomic registers is addressed in this technical paper. In particular, it presents the construction of a single-writer, multiple-reader atomic register from single-writer, single-reader atomic registers. The construction of a single-writer, M-reader, N-bit atomic register requires O ( M 2 + M N ) shared single-writer, single-reader safe bits. This is asymptotically optimal.
The paper is organized into sections that define the problem of constructing an M-reader atomic register from single-reader atomic registers; present the construction; informally describe the construction; and give a formal correctness proof.
The definition of atomicity is equivalent to that given by J. Misra [1]. His axioms require that all read and write operations be shrunk to a point. A formal correctness proof is presented for the multiple-reader atomic register construction. Alternative methods for proving correctness are discussed, including a recursive construction method.
The paper will interest specialists researching or implementing atomic registers. It is not tutorial and is probably not of general interest to practitioners. It is well written and contains an excellent list of references.
