Locality and Availability in Distributed Storage

By Ankit Singh Rawat, Dimitris Papailiopoulos, A. Dimakis, Sriram Vishwanath. 2014

269 citations recorded by the source corpus.

This paper studies the problem of information symbol availability in codes: we refer to a systematic code as code with (r, t)-availability if every information (systematic) symbol can be reconstructed from t disjoint groups of other code symbols, each of the sizes at most r. This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum Hamming distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a tradeoff between rate, minimum Hamming distance, and availability parameters. Our codes match the aforementioned bound, and their constructions rely on certain combinatorial structures. Resolvable designs provide one way to realize these required combinatorial structures. The two constructions presented in this paper require field sizes, which are linear and exponential in the code length, respectively. From a practical standpoint, our codes are relevant for distributed storage applications involving hot data, i.e., the information, which is frequently accessed by multiple processes in parallel.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “This is a useful load balancing property that has significant applications in distributed storage [66].”
Batch codes through dense graphs without short cycles (2014, background): “The weaker problem of enabling multiple parallel reads of a single symbol was recently investigated in [17]–[19].”
Analyzing the download time of availability codes (2015, methodology): “SIMULATION RESULTS In this section, we simulate the fork-join queueing model in the high arrival rate scenario for the codes given in Table I: a (30, 15, 3, 2)-LRC in [1], a (30, 15, 2, 1)-LRC in [8], an 8-replication scheme that is effectively a (120, 15, 1, 7)-LRC, and a (30, 15)-MDS code.”
Optimal binary switch codes with small query size (2015, background): “[3], [4], [5], [6]), but known codes for the latter model do not give request lengths R close to k.”