Locality and Availability in Distributed Storage

DOI10.1109/TIT.2016.2524510MaRDI QIDQ2976662zbMATH OpenFDO

Authors A. S. Rawat, Dimitris S. Papailiopoulos, Alexandros G. Dimakis, Sriram Vishwanath

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.2011

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Abstract: This paper studies the problem of code symbol availability: a code symbol is said to have $(r,t)$-availability if it can be reconstructed from $t$ disjoint groups of other symbols, each of size at most $r$. For example, $3$-replication supports $(1,2)$-availability as each symbol can be read from its $t=2$ other (disjoint) replicas, i.e., $r=1$. However, the rate of replication must vanish like $frac1t+1$ as the availability increases. 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 distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a trade-off between minimum distance, availability and locality. Our codes match the aforementioned bound and their construction relies on combinatorial objects called resolvable designs. From a practical standpoint, our codes seem useful for distributed storage applications involving hot data, i.e., the information which is frequently accessed by multiple processes in parallel.

Cited in

(28)

• Anticode-based locally repairable codes with high availability
• Architecture-aware coding for distributed storage: repairable block failure resilient codes
• Multiset combinatorial batch codes
• RS-like locally recoverable codes with intersecting recovering sets
• Regular \((k, R, 1)\)-packings with \(\max(R)=3\) and their locally repairable codes
• On the locality of quasi-cyclic codes over finite fields
• Linear programming bounds for distributed storage codes
• Two classes of optimal LRCs with information (r, t)-locality
• The complete hierarchical locality of the punctured simplex code
• PIR codes with short block length
• Embedded minimal disks: Proper versus nonproper—global versus local
• scientific article; zbMATH DE number 5259998 (Why is no real title available?)
• Codes for Distributed Storage
• Codes in the sum-rank metric: fundamentals and applications
• A family of codes with variable locality and availability
• Locally repairable codes with multiple repair sets based on packings of block size 4
• Optimal ternary locally repairable codes
• Some new constructions of optimal linear codes and alphabet-optimal \((r, \delta)\)-locally repairable codes
• On finding the largest minimum distance of locally recoverable codes: a graph theory approach
• Easy repair via codes with simplex locality
• Locally recoverable algebro-geometric codes from projective bundles
• A class of locally recoverable codes over finite chain rings
• Optimal locally repairable codes with multiple repair sets based on 2-regular packings
• On the data persistency of replicated erasure codes in distributed storage systems
• Hull dimension of optimal binary LRCs with availability
• Locally maximal recoverable codes with unequal localities and LMR codes with hierarchical locality
• Binary t-divisible codes via simplicial complexes and their applications
• Optimal RS-like LRC codes of arbitrary length

This page was built for publication: Locality and Availability in Distributed Storage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976662)