PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization

Min Ye, Alexander Barg

arXiv:1605.08630v4cs.IT

TL;DR

The paper addresses how to construct optimal-access MDS codes with sub-packetization closer to the lower bound, while also extending repair to grouped nodes. It gives explicit low-complexity constructions for both settings with stated finite-field size conditions.

  • Problem

    The paper asks how to reduce the sub-packetization of explicit optimal-access MDS codes toward the lower bound and how to model optimal repair when nodes form local groups.

  • Method

    The paper constructs explicit MDS array-code families using matrix parity-check equations, including ordinary optimal-access and group-repair variants.

  • Results

    The constructions achieve optimal access with l = r^⌈n/r⌉ and group optimal access for n = sm codes with r ≥ s.

  • Takeaways & Limitations

    Optimal-access MDS codes can be constructed for any n and r, while group repair supports flexible local-group configurations.

Abstract

from arXiv · show

An $(n,k,l)$ MDS array code of length $n,$ dimension $k=n-r$ and sub-packetization $l$ is formed of $l\times n$ matrices over a finite field $F,$ with every column of the matrix stored on a separate node in a distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node can be performed by accessing a set of $d\le n-1$ helper nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimal-access MDS codes with $d=n-1,$ the sub-packetization $l$ satisfies the bound $l\ge r^{(k-1)/r}.$ In our previous work, for any $n$ and $r,$ we presented an explicit construction of optimal-access MDS codes with sub-packetization $l=r^{n-1}.$ In this paper we take up the question of reducing the sub-packetization value $l$ to make it approach the lower bound. We construct an explicit family of optimal-access codes with $l=r^{\lceil n/r\rceil},$ which differs from the optimal value by at most a factor of $r^2.$ These codes can be constructed over any finite field $F$ as long as $|F|\ge r\lceil n/r\rceil,$ and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), calling it group repair with optimal access. In this variation, we assume that the set of $n=sm$ nodes is partitioned into $m$ repair groups of size $s,$ and require that the amount of accessed data for repair is the smallest possible whenever the $d$ helper nodes include all the other $s-1$ nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field $F$ of size $|F|\ge n,$ and also afford low-complexity encoding and decoding procedures.

I. INTRODUCTION

Distributed storage systems use MDS array codes to recover failed nodes, but repair also consumes network bandwidth and disk I/O. This motivates minimizing both transferred and accessed data.

  • MDS array codes provide universal node recovery regardless of which nodes fail.They recover missing data using information stored in functional nodes.
  • Repair bandwidth measures transferred data, while accessed volume corresponds to disk I/O operations.
  • Recent MDS-code research therefore targets reductions in repair bandwidth and accessed data.Dimakis et al. established lower bounds on repair bandwidth that motivated subsequent work.

A. Exact-repair regenerating codes

The paper formalizes repair access and bandwidth for MDS array codes, reviews their lower bounds and constructions, and targets explicit optimal-access codes with substantially smaller sub-packetization.

  • An MDS array code stores l-dimensional column coordinates across n nodes, with any k columns recovering the remaining r columns.The code has length n, dimension k, redundancy r=n−k, and sub-packetization l.
  • Repair downloads functions of helper-node data, while access counts the accessed symbols used by the repair procedure.The quantities ω_i(R_i) and β_i(R_i) measure accessed and downloaded symbols, respectively.
  • The repair-bandwidth lower bound is achieved with all n−1 surviving nodes as helpers.The bound decreases as the number of helpers increases.
  • Optimal-access codes attain the repair-access lower bound, making them a subclass of optimal-repair MDS codes.The paper distinguishes access from repair bandwidth and notes that optimal access implies optimal repair.
  • Optimal-access MDS codes satisfy l ≥ r^(k−1)/r, while prior explicit constructions had l = r^(n−1).Earlier constructions with smaller sub-packetization often required large fields or restricted parameters.
  • The paper constructs explicit optimal-access codes with l = r^⌈n/r⌉, within a factor of at most r^2 of the lower bound.They require |F| ≥ r⌈n/r⌉ and have low-complexity encoding and decoding.

B. Repair groups and node regeneration: Group optimal access property

The paper introduces group repair for storage systems whose nodes are partitioned into locally connected groups, and constructs codes achieving optimal access when helpers include the failed node’s local peers.

  • Group repair partitions n = sm nodes into m groups of size s, with stronger connectivity within each group.The model reflects settings where local links are geographically or otherwise more stable.
  • The group-repair problem connects regenerating codes with locality-constrained codes such as LRCs.Related work also studies local regeneration and helper selection under varying conditions.
  • Group optimal access requires optimal access when the d = s+k−1 helpers include all s−1 nodes in the failed node’s group.
  • The group-repair access volume meets the lower bound for the specified helper configuration.
  • The paper constructs explicit (n = sm, k = n−r, l = sm) codes with group optimal access for r ≥ s.The codes support any number of groups and group sizes s≤r, require |F|≥n, and have low-complexity encoding and decoding.

II. CODE CONSTRUCTION

The construction defines MDS array codes through matrix parity-check equations and digit-coordinate transformations, with variants covering divisible and nondivisible code lengths.

  • The code consists of column vectors satisfying r matrix parity-check equations over a finite field.The code is defined by A_t,i C_i = 0 for t=0,…,r−1.
  • Construction 1 uses s-ary coordinate expansions and matrices indexed by digit positions, digit values, and parity checks.It requires s≤r≤sm, n=sm, l=s^m, and |F|≥n.
  • The resulting code has the MDS property; when s=r it has optimal access, and when s<r it has group optimal access.
  • Construction 2 extends the approach to code lengths n=rm+r′ that are not divisible by r.It uses l=r^(m+1) and a field with |F|≥r(m+1).

III. THE MDS PROPERTY

The section introduces an example used to visualize Construction 1 and provide intuition for the proof of its MDS property.

  • The example illustrates how the construction's defining equations operate and motivates the subsequent MDS-property proof.The authors note that the formal proof notation is difficult to visualize, so the example supplies intuition.

A. Example

For s = r = 3 and m = 2, the construction gives an (n,l)=(6,9) example over any field of size at least 6. Its MDS verification reduces to showing a matrix has trivial null space.

  • Example: For s = r = 3 and m = 2, the example has n = 6 and l = 9.It can be realized over any field with |F| ≥ 6, including F7.
  • Example: The MDS property requires every 3 × 3 block submatrix of the associated 3 × 6 block matrix to be invertible.Here, each block is an l × l matrix.
  • Example: The proof permutes the rows of B using a permutation matrix P to obtain D = PB without changing rank.The permutation is specified by Pij = 1 iff i = (j − j mod 9)/9 + 3(j mod 9).
  • Example: Distinct coefficients λi force selected variables to zero, after which elimination reduces the system further.The first elimination yields x2 = x8 = x11 = x17 = x20 = x26 = 0.
  • Example: The remaining equations similarly force all variables to zero, proving that B is invertible.The argument concludes with x3 = x4 = x21 = x12 = x13 = x22 = 0, together with the earlier eliminations.

B. A proof of the MDS property

The proof establishes the MDS property by analyzing transformed parity-check submatrices, identifying suitable row groups, and inductively eliminating variables until only the zero solution remains.

  • B. A proof of the MDS property: For any r selected nodes, the construction's MDS proof reduces to showing that an associated matrix B is invertible.Equivalently, every vector X satisfying the corresponding homogeneous system must be zero.
  • B. A proof of the MDS property: The proof partitions the transformed matrix into r-row strips and groups nonzero columns according to the node-index sets U(a) and J(a).The sets J(a)(i) partition J(a) by the column types Li and γLi.
  • B. A proof of the MDS property: A suitable strip index a is chosen so that U(a) equals the r selected node indices, enabling Vandermonde-based elimination of variables.The construction chooses the digits of a to avoid selected indices in groups not fully represented among the chosen nodes.
  • B. A proof of the MDS property: The proof repeatedly eliminates variables from reduced systems, using induction on the cardinality of U(a), until every variable is shown to be zero.The example's reduced matrix has dimension r(l−|S|) by r(l−|S|), and the process continues until no variables remain.
  • B. A proof of the MDS property: Theorem 1 concludes that Construction 1 is an (n = sm, k = n − r, l = sm) MDS array code.The proof applies to every choice of r indices among the n nodes.
  • B. A proof of the MDS property: Corollary 4 states that Construction 2 is an (n = rm + r′, k = n − r, l = rm+1) MDS array code.

IV. THE OPTIMAL ACCESS PROPERTY

The construction supports optimal-access repair by recovering each failed node from designated coordinate subsets; setting s = r yields optimal access for all code lengths.

  • IV. THE OPTIMAL ACCESS PROPERTY: The repair derivation separates helper-node contributions according to whether aq is greater than, equal to, or less than w.These cases determine whether a row contains one nonzero entry or s nonzero entries.
  • IV. THE OPTIMAL ACCESS PROPERTY: The failed node is determined entirely from the elements in the designated set C(v,u).The remaining terms in the repair equation are recoverable from this set, so the whole node follows from those coordinates.
  • IV. THE OPTIMAL ACCESS PROPERTY: When s = r, Construction 1 has the optimal access property because each helper contributes exactly a 1/r fraction of its coordinates.
  • IV. THE OPTIMAL ACCESS PROPERTY: Construction 2 also has the optimal access property, extending the result to code lengths not divisible by r.

A. Group optimal access

The section establishes group optimal access for Construction 1 by showing that selected coordinates in a repair group are determined from corresponding coordinates in any k external helpers. The proof reduces the resulting equations to a full-rank system using linear independence of associated vectors.

  • Theorem 8 states that Construction 1 has the (s, s + k −1)-group optimal access property.
  • Lemma 9 asserts that coordinates in the failed node’s repair subset are determined by the corresponding subsets from any k nodes in N(v).
  • For each failed node, repair uses its other s−1 group members plus any k helpers outside the group, accessing exactly a 1/s fraction from each helper.
  • The proof permutes parity-check equations, partitions the resulting matrix into r-row blocks H(a), and derives the system used for recovery.
  • After eliminating terms from nonselected helpers, the proof obtains (r−s)l/s equations in (r−s)l/s unknowns.
  • Linear independence of every r−s transformed vector in N(v) implies the unknown elements vanish, completing the proof of the theorem.

V. CONCLUSION

The conclusion presents explicit optimal-access MDS codes with sub-packetization l = r^⌈n/r⌉ and field size |F| ≥ r⌈n/r⌉. It also identifies an open problem concerning smaller fields for systematic optimal repair.

  • The construction achieves nearly optimal sub-packetization l = r⌈n/r⌉ with field size |F| ≥ r⌈n/r⌉.
  • The field-size requirement |F| ≥ r⌈n/r⌉ is described as just slightly greater than n.
  • Systematic optimal repair can use smaller sub-packetization l = r⌈k/(r+1)⌉ when the base field is sufficiently large.
  • Explicit constructions over small fields for that systematic-repair sub-packetization remain open for general r.
Loading 1605.08630v4…