2015/07/18 by Alexander Spiegelman, Spiegelman, Alexander, Yuval Cassuto +5
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1507.05169
openalex publication_date 2015/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. 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.