Practically Stabilizing Atomic Memory

2010/07/11 by Alon, Noga, Attiya, Hagit, Dolev, Shlomi +3
#Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1007.1802

Abstract

A self-stabilizing simulation of a single-writer multi-reader atomic register is presented. The simulation works in asynchronous message-passing systems, and allows processes to crash, as long as at least a majority of them remain working. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme that can accommodate arbitrary labels, i.e., including those not generated by the scheme itself.

Related

• Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems
• Simulating a Shared Register in a System that Never Stops Changing
• Self-stabilization Overhead: an Experimental Case Study on Coded Atomic Storage
• A Coded Shared Atomic Memory Algorithm for Message Passing Architectures
• Storage-Efficient Shared Memory Emulation