The Collective Memory of Amnesic Processes

This paper considers the problem of robustly emulating a shared atomic memory over a distributed message passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduce a generic algorithm that emulates an atomic memory. The algorithm is instantiated for various settings according to whether processes have access to local stable storage, and whether, in every execution of the algorithm, a sufficient number of processes are assumed not to crash. We establish the optimality of specific instances of our algorithm in terms of resilience, log-complexity (number of stable storage accesses needed in every read or write operation), as well as time-complexity (number of communication steps needed in every read or write operation). The paper also discusses the impact of considering a multi-writer versus a single-writer memory, as well as the impact of weakening the consistency of the memory, by providing safe or regular semantics instead of atomicity.