Almost Optimal Single Reader, Single Writer Atomic Register
Prasad Jayanti, James E. Burns, Gary L. Peterson · Journal of Parallel and Distributed Computing · 2000
Lamport defined three classes of communication registers: safe, regular, and atomic. Wait-free implementations of one register class from a weaker class abound in the literature. However, results establishing the intrinsic complexity of such implementations are relatively scarce. In this paper, we consider the problem of implementing an n -valued single reader, single writer atomic register A from two regular registers, BUF and R , where BUF is a regular register that only the writer of A can write and R is a regular register that only the reader of A can write. (Lamport proved that there cannot be an implementation without R , so R is at least 2-valued in any implementation.) We present an almost space optimal implementation. Specifically, our results are: (1) An implementation for which BUF is 2 n -valued and R is 2-valued; and (2) A lower bound stating that, in any implementation, regardless of how large R is, BUF must be at least (2 n −1)-valued.