On Concurrent Reading and Writing

This paper came out of my study of the bakery algorithm of [12]. The problem with that algorithm is that it requires unbounded state. To allow the state to be bounded in practice, I needed an algorithm for reading and writing multidigit numbers, one digit at a time, so that a read does not obtain too large a value if it overlaps a write. This paper shows that this can be done by simply writing the digits in one direction and reading them in the other. It also has some other nice algorithms. The paper assumes that reading and writing a single digit are atomic operations. The original version introduced the notion of a regular register and proved the results under the weaker assumption that the individual digits were regular. However, the editor found the idea of nonatomic reads and writes to individual digits too heretical for CACM readers, and he insisted that I make the stronger assumption of atomicity. So, the world had to wait another decade, until the publication of [70], to learn about regular registers.