Space Bounds for Reliable Multi-Writer Data Store: Inherent Cost of Read/Write Primitives

Reliable storage emulations from fault-prone components have established themselves as an algorithmic foundation of modern storage services and applications. Most existing reliable storage emulations are built from storage services supporting arbitrary read-modify-write primitives. Since such primitives are not typically exposed by pre-existing or off-the-shelf components (such as cloud storage services or network-attached disks) it is natural to ask if they are indeed essential for efficient storage emulations. In this paper, we answer this question in the affirmative. We show that relaxing the underlying storage to only support read/write operations leads to a linear blow-up in the emulation space requirements. We also show that the space complexity is not adaptive to concurrency, which implies that the storage cannot be reliably reclaimed even in sequential runs. On a positive side, we show that Compare-and-Swap primitives, which are commonly available with many off-the-shelf storage services, can be used to emulate a reliable multi-writer atomic register with constant storage and adaptive time complexity.