PaperlayerView exact revision on arXiv

Source-linked AI summary

Locality and Availability in Distributed Storage

Ankit Singh Rawat, Dimitris S. Papailiopoulos, Alexandros G. Dimakis, Sriram Vishwanath

arXiv:1402.2011v1cs.IT

TL;DR

The paper asks how distributed storage codes can provide multiple low-locality reconstruction options without the vanishing rate imposed by replication. It derives distance bounds and constructs availability codes using combinatorial structures, achieving constant rate, scaling parallel reads, and distance arbitrarily close to the Singleton bound. The results target frequently accessed hot data.

  • Problem

    Replication supports parallel reads but its rate vanishes as availability increases, motivating codes with high availability and low locality at nonvanishing rate.

  • Method

    The paper derives minimum-distance bounds for linear (n, k, r, t)-LRCs and constructs optimal codes using designs, Pyramid codes, and Gabidulin codes.

  • Results

    The constructions support scaling availability at arbitrarily high constant rate while keeping minimum distance arbitrarily close to the Singleton bound.

  • Takeaways & Limitations

    The codes are presented as useful for distributed storage applications involving hot data accessed frequently by multiple processes in parallel.

Abstract

from arXiv · show

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 $\frac{1}{t+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.

I. INTRODUCTION

The paper introduces availability for parallel reconstruction in distributed storage and develops codes that combine high availability and locality with constant rate and near-MDS distance. It targets hot data, where blocks may be accessed concurrently by multiple jobs.

  • 3-replication provides three parallel reads with locality r = 1, but increasing replication makes the rate vanish like 1/(t+1).
  • Codes can support scaling parallel reads at an arbitrarily high constant rate, including availability t = Θ(k^1/3−ϵ) and locality r = Θ(k^1/3).
  • The constructions address hot data, which is frequently accessed and may be read concurrently by multiple system jobs.
  • The paper first derives a minimum-distance bound for linear (n, k, r, t)-LRCs with one local parity per repair group.
  • Optimal codes exist for selected sublinear locality and availability regimes, with distance asymptotically equal to that of an (n, k) MDS code.
  • Availability requires t disjoint repair groups, each containing at most r other symbols that can reconstruct the desired information symbol.

III. UPPER BOUND ON MINIMUM DISTANCE OF (n, k, r, t)-LRCS

The section derives upper bounds on minimum distance for locally repairable codes with availability, first under linearity and single-parity repair groups, then more generally. The resulting bound generalizes the usual locality bound and its tightness is discussed across code regimes.

  • The membership matrix R has m local-group columns, each involving at most r information symbols, while every information symbol appears in at least t groups.Counting incidences yields the key inequality mr ≥ kt.
  • Theorem 1 bounds the distance of linear (n, k, r, t)-LRCs when every repair group contains exactly one parity symbol.The proof constructs an unrecoverable symbol set using the local-parity structure represented by R.
  • The proof handles separately rows of R with exactly t ones and rows with minimum weight t′ > t, then combines the resulting cases.For the first case, an unrecoverable set has size at least k − 1 + m − t; the second uses rt′ ≤ mr.
  • For t = 1, the specialized bound reduces to the known distance bound for codes with r-locality.Prior work established the general bound for linear codes and asymptotic zero-rate achievability, while tightness at high rate remained open.
  • Theorem 2 gives a more general minimum-distance bound for linear or nonlinear (n, k, r, t)-LRCs without requiring one parity per repair group.Thus the general result relaxes both the linearity assumption and the single-local-parity condition.

IV. ACHIEVABILITY RESULTS FOR (n, k, r, t)-LRCS

The paper develops explicit availability-code constructions and analyzes their distance, using resolvable designs and Gabidulin codes as supporting structures. These constructions target parallel access to frequently accessed storage data.

  • The paper presents explicit constructions for codes with (r, t)-availability and analyzes their minimum distance.The construction section includes modified Pyramid codes, Gabidulin-code-based all-symbol locality, and resolvable-design methods.
  • Resolvable designs are introduced as combinatorial objects used in the proposed code constructions.The paper provides their definition and incidence-matrix representation before applying them to availability codes.
  • A 2-(k, b, c, r, λ)-resolvable design uses size-r blocks, constant pair coverage λ, and c parallel classes that partition the point set.The incidence matrix records which points belong to which blocks.
  • Gabidulin codes are maximum-rank-distance codes and are MDS, providing an algebraic component for one construction route.Their encoding evaluates a data polynomial at linearly independent points over an extension field.

C. Construction of (n, k, r, t)-LRCs

Construction I builds availability codes from a binary matrix whose column supports form t partitions and whose row intersections are tightly controlled. The matrix can be derived from an MDS generator matrix by splitting selected parity columns.

  • Assumption 1 requires a k × (tk/r) binary matrix R whose columns have weight r and whose supports form t partitions of [k].The supports of any two rows may intersect in at most one position.
  • The matrix columns are grouped into R1, …, Rt, with each group containing k/r columns whose supports form one partition of [k].These groups organize the local parities associated with the t availability classes.
  • Starting from a systematic (N + t, k) MDS generator matrix, Construction I retains the first N columns and splits each of t parity columns into k/r weight-r columns.The split-column supports are specified by the corresponding groups of R.
  • The resulting generator matrix has systematic symbols, global parities, and local-parity columns created from the split MDS parity columns.This construction preserves the MDS-based global structure while adding local repair groups.

1) Construction I: •

Construction I modifies an MDS-based Pyramid-style code by splitting parity columns according to partitions, producing disjoint repair groups and distance matching the stated bound. A concrete example yields a (30, 15, 3, 2)-LRC with ten local parities.

  • Construction I: Construction I retains the first N columns of the MDS generator matrix and splits its final t columns into weight-r local-parity columns.The resulting generator matrix separates systematic symbols, global parities, and local parities.
  • Construction I: Resolvable designs provide one way to construct R by taking columns from the incidence matrix associated with t parallel classes.Each parallel class supplies a partition, and its blocks determine local-parity supports.
  • Construction I: A (30, 15, 3, 2)-LRC uses a systematic (22, 15) MDS code and produces t k/r = 10 local parities by splitting two parity columns.The example is obtained by splitting the columns corresponding to p6 and p7.
  • Construction I: The example has (3, 2)-availability: m1 has repair groups {m2, m3, l1} and {m5, m6, l6}.The same construction also gives two repair groups for m15.
  • Construction I: Theorem 3 states that Construction I produces an (n, k, r, t)-LRC attaining the distance bound in (6).Its proof establishes correction of n − k − r + t = N − k + t node erasures.
  • Construction I: The support conditions on R ensure each systematic symbol is covered by t local parities of weight r with disjoint repair groups.The non-overlap requirement distinguishes this construction from the original Pyramid codes.

D. Construction of (n, k, r, t)-LRCs with all-symbol locality

Gabidulin codes are used to construct (n, k, r, t)-LRCs with all-symbol locality under divisibility and structural assumptions.

  • Gabidulin codes provide the basis for constructing (n, k, r, t)-LRCs with all-symbol locality.

1) Construction II:

Construction II extends a code produced from a transformed Gabidulin generator matrix by adding local parities for all-symbol locality, while preserving availability and distance guarantees.

  • Construction II starts from a transformed Gabidulin generator matrix and a code obtained using Construction I.
  • Step 2 partitions systematic symbols and global parities into groups of size r, then adds local parities for these groups.
  • The resulting code is an (n, k, r, t)-LRC with all-symbol locality when the stated divisibility and assumption conditions hold.
  • The structure of the matrix R supplies all-symbol locality and (r, t)-availability.
  • The construction recovers original message symbols after any pattern of n − k − r + t node erasures.
  • In the second erasure case, surviving local parities are combined to obtain additional global-parity evaluations, yielding k independent evaluations for message recovery.

E. Explicit designs of R for Constructions I and II

The paper constructs the matrix R using resolvable designs and zigzag-code ideas, obtaining codes with scaling locality and availability while keeping distance orderwise close to MDS codes.

  • The matrix R uses a 0/1 incidence structure whose column and row supports satisfy the construction assumptions.
  • Resolvable designs with sufficiently many parallel classes provide matrices R for the proposed LRC constructions.
  • Codes from these designs achieve r = Θ(k^1/3) and t = r^1−ϵ.
  • The resulting distance is n − k − k·o(1) + o(k) + 1, orderwise matching the distance of an (n, k)-MDS code.
  • For fixed rate, the rate tends to 1 under scaling, so suitable parameters permit rate arbitrarily close to 1.
  • A zigzag-code-based construction supports r = Θ(log(k) log log(k)) and t = Θ(r^1−ϵ), with orderwise MDS distance.
  • The explicit construction described is not a 2-design because some pairs need not occur in exactly one block.

V. CONCLUSIONS AND OPEN PROBLEMS

The paper identifies open questions about explicit constructions, nonlinear-code trade-offs, parameter regimes, and concurrent reads of different symbols. It also points to hot-data applications while noting that their benefits remain to be quantified.

  • Explicit codes attaining the general distance bound in Theorem 2 remain an open question.
  • It remains unclear whether the distance-locality-availability trade-off in Theorem 1 extends to nonlinear codes.
  • High-availability codes are not known to exist for several choices of parameters (n, k, r, t).The necessity of resolvable-design requirements and whether other methods yield significantly better parameters are also unresolved.
  • The constructions support multiple reads of each symbol but provide no guarantees for concurrent reads of two different symbols.The paper suggests quantifying such arbitrary parallel reads through bounds, queuing models, or system measurements.

APPENDIX A PROOF OF THEOREM 2

The proof constructs a sub-code by iteratively fixing coordinates across repair groups, then punctures fixed coordinates and applies the Singleton bound. It transfers the resulting distance bound back to the original code.

  • The proof follows a Forbes–Yekhanin technique to upper-bound minimum distance for a non-linear systematic code with locality r.
  • The algorithm repeatedly selects a coordinate outside previously fixed repair-group coordinates and fixes the most frequent restriction across its t disjoint local groups.
  • When a selected restriction leaves a singleton sub-code, the construction chooses a maximal subset preserving multiple codewords before continuing.
  • At termination, puncturing the fixed coordinates produces C′′ with the same size and minimum distance as C′, after which the Singleton bound is applied.The punctured code has length n−|Rℓ|.
  • The distance bound is then combined with the preceding inequalities and transferred to the original code using dmin(C) ≤ dmin(C′′) = dmin(C′).
Loading 1402.2011v1…