Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory. Oh-RAM! One and a half round read/write atomic memory

Emulating atomic read/write shared objects in a message- passing system is a fundamental problem in distributed computing. Considering that network communication is the most expensive resource, efficiency is measured first of all in terms of the communication needed to implement read and write operations. It is well known that two commu- nication round-trip phases involving in total four message exchanges are sufficient to implemented atomic operations. In this work we present a comprehensive treatment of the question of when and how it is possible to implement atomic memory where read and write operations complete in three message exchanges, i.e., we aim for One and half Round Atomic Memory, hence the name Oh-RAM! We present al- gorithms that allow operations to complete in three commu- nication exchanges without imposing any constraints on the number of readers and writers. We present an implementa- tion for the single-writer/multiple-reader (SWMR) setting, where reads complete in three communication exchanges and writes complete in two exchanges. Then we pose the question of whether it is possible to implement multiple- writer/multiple-reader (MWMR) memory where operations complete in at most three communication exchanges. We answer this question in the negative by showing that an atomic memory implementation is impossible if both read and write operations take three communication exchanges, even when assuming two writers, two readers, and a single replica server failure. Motivated by this impossibility re- sult, we provide a MWMR atomic memory implementation where reads involve three and writes involve four communi- cation exchanges. In light of our impossibility result these algorithms are optimal in terms of the number of commu- nication exchanges.