Optimal Register Construction in M&M Systems

Motivated by recent distributed systems technology, Aguilera et al. introduced a hybrid model of distributed computing, called message-and-memory model or m&m model for short [Marcos K. Aguilera et al., 2018]. In this model, processes can communicate by message passing and also by accessing some shared memory. We consider the basic problem of implementing an atomic single-writer multi-reader (SWMR) register shared by all the processes in m&m systems. Specifically, we give an algorithm that implements such a register in m&m systems and show that it is optimal in the number of process crashes that it can tolerate. This generalizes the well-known implementation of an atomic SWMR register in a pure message-passing system [Attiya et al., 1995]