2015/08/15 by Gregory Chockler, Chockler, Gregory, Dan Dobre +5
Computer Science · Engineering · #Advanced Data Storage Technologies #C.2.4 #C.4 #D.4.7 #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1508.03762
openalex publication_date 2015/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Reliable storage emulations from fault-prone components have established\nthemselves as an algorithmic foundation of modern storage services and\napplications. Most existing reliable storage emulations are built from storage\nservices supporting arbitrary read-modify-write primitives. Since such\nprimitives are not typically exposed by pre-existing or off-the-shelf\ncomponents (such as cloud storage services or network-attached disks) it is\nnatural to ask if they are indeed essential for efficient storage emulations.\nIn this paper, we answer this question in the affirmative. We show that\nrelaxing the underlying storage to only support read/write operations leads to\na linear blow-up in the emulation space requirements. We also show that the\nspace complexity is not adaptive to concurrency, which implies that the storage\ncannot be reliably reclaimed even in sequential runs. On a positive side, we\nshow that Compare-and-Swap primitives, which are commonly available with many\noff-the-shelf storage services, can be used to emulate a reliable multi-writer\natomic register with constant storage and adaptive time complexity.\n