Constructing two-writer atomic registers. (English) Zbl 0663.68034

This paper gives a construction of a two-writer, n-reader atomic memory register from two one-writer, \((n+1)\)-reader atomic memory registers. There are no restrictions on the size of the constructed register. The simulation requires only a single extra bit per real register, and can survive the failure of any set of readers and writers. A complete proof of correctness is given.


68N25 Theory of operating systems
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI