Space Bounds for Reliable Storage: Fundamental Limits of Coding

We study the inherent space requirements of shared storage algorithms in asynchronous fault-prone
systems. Previous works use codes to achieve a better storage cost than the well-known replication
approach. However, a closer look reveals that they incur extra costs somewhere else: Some use
unbounded storage in communication links, while others assume bounded concurrency or synchronous
periods. We prove here that this is inherent, and indeed, if there is no bound on the concurrency level,
then the storage cost of any reliable storage algorithm is at least f + 1 times the data size, where f
is the number of tolerated failures. The lower bound is information theoretic - it applies to any storage
algorithm, whether coded or uncoded. We further present a technique for combining erasure-codes with
full replication so as to obtain the best of both. We present a storage algorithm whose storage cost is
close to the lower bound in the worst case, and adapts to the concurrency level when it is low.

Joint work with Alexander Spiegelman, Yuval Cassuto, and Gregory Chockler