PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit constructions of high-rate MDS array codes with optimal repair bandwidth

Min Ye, Alexander Barg

arXiv:1604.00454v2cs.IT

TL;DR

High-rate MDS array codes need explicit constructions that achieve optimal repair beyond single failures repaired from all surviving nodes. This paper presents two families covering all h≤r and k≤d≤n-h simultaneously, with low complexity, optimal access in the second family, and universally error-resilient repair.

  • Problem

    High-rate MDS array-code constructions with optimal repair were limited in explicitness and repair scope, motivating codes supporting multiple erased nodes and helper counts.

  • Method

    The paper constructs two explicit MDS array-code families using structured parity-check matrices, diagonal or permutation matrices, and least-common-multiple subpacketization.

  • Results

    The families achieve universally error-resilient (h,d)-optimal repair for all h≤r and k≤d≤n-h simultaneously; the second also has optimal access over fields with |F|≥n+1.

  • Takeaways & Limitations

    The constructions provide explicit high-rate MDS array codes spanning the full allowed erasure and helper ranges, with optimal access available over fields of size at least n+1.

Abstract

from arXiv · show

Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure-tolerance for a given number of parity nodes. Suppose that an MDS code with $k$ information nodes and $r=n-k$ parity nodes is used to encode data in a distributed storage system. It is known that if $h$ out of the $n$ nodes are inaccessible and $d$ surviving (helper) nodes are used to recover the lost data, then we need to download at least $h/(d+h-k)$ fraction of the data stored in each of the helper nodes (Dimakis et. al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any $h$ erased nodes from any $d$ helper nodes, we say that the MDS code has the $(h,d)$-optimal repair property. We study high-rate MDS array codes with the optimal repair property. Explicit constructions of such codes in the literature are only available for the cases where there are at most 3 parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any $r$ and $n$, we present two explicit constructions of MDS array codes with the $(h,d)$-optimal repair property for all $h\le r$ and $k\le d\le n-h$ simultaneously. Codes in the first family can be constructed over any base field $F$ as long as $|F|\ge sn,$ where $s=\text{lcm}(1,2,\dots,r).$ The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field $F$ as long as $|F|\ge n+1.$ Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property.

I. INTRODUCTION

The paper addresses high-rate MDS array-code repair in distributed storage, where failures are frequent and downloading data across nodes is costly. It introduces explicit code families that simultaneously support optimal repair across erased-node counts and helper-set sizes, including error resilience and optimal access.

  • Motivation and notation: MDS array codes store each node as a vector while allowing any k of n nodes to recover the codeword.Each code has k information nodes, r=n-k parity nodes, and subpacketization l over a finite field F.
  • Motivation and notation: The repair lower bound requires downloading at least h/(d+h-k) of each helper node’s data when h nodes are repaired from d helpers.Achieving this bound for every erased and helper-node choice defines the (h,d)-optimal repair property.
  • Motivation and notation: Optimal access further requires meeting the repair lower bound by directly accessing data rather than downloading arbitrary functions of helper contents.The paper also considers universally error-resilient repair, which tolerates erroneous helper nodes during recovery.
  • Prior work: Prior high-rate constructions mainly handled single systematic-node failures using all surviving nodes, with earlier explicit availability limited in parity count or repair scope.The cited literature includes broader existence results, but not the simultaneous construction target addressed here.
  • Paper contributions: The paper presents two explicit families supporting universally error-resilient optimal repair for every h≤r and k≤d≤n-h simultaneously.The first family has low-complexity procedures; the second has optimal access and requires only |F|≥n+1.
  • Paper contributions: Additional constructions include Generalized Reed-Solomon array codes with smaller subpacketization and optimal repair for several helper counts.The conclusion identifies constant-size fields and smaller l as remaining open problems.

III. CONSTRUCTION OF MDS ARRAY CODES WITH OPTIMAL REPAIR PROPERTY

Construction 1 uses diagonal matrices and a large field to produce MDS array codes whose repair, encoding, decoding, and updates can be performed with structured low-dimensional operations. The construction achieves optimal single-node repair and optimal updates.

  • Construction: Construction 1 uses l=r^n and requires a field with |F|≥r^n containing r^n distinct coefficients.Its parity-check construction is organized through diagonal matrices indexed by node and coordinate digits.
  • Repair: Each surviving node transmits one field element to recover r coordinates in a failed node, attaining optimal repair bandwidth.The downloaded symbols are selected through coordinate permutations indexed by the failed node and repair grouping.
  • Complexity: Repair can use r×r matrix operations instead of l×l matrices, reducing the computational dimension of the procedure.The same structured parity-check form also supports efficient encoding and decoding.
  • MDS property: The resulting code is MDS because every r columns of each coordinate-level parity-check matrix have rank r.Therefore, any k nodes recover the complete codeword.
  • Updates: Updating one information coordinate requires updating one corresponding coordinate in every parity node, making the construction an optimal update code.This matches the minimum imposed by the MDS property.

IV. EXPLICIT MDS ARRAY CODES WITH THE UER d-OPTIMAL REPAIR PROPERTY

Construction 2 extends the diagonal-matrix approach to repair from arbitrary helper counts using Generalized Reed-Solomon structure. It provides universally error-resilient d-optimal repair while retaining MDS, low-complexity operations, and optimal updates.

  • Construction: For a chosen d, Construction 2 sets s=d+1-k, l=s^n, and requires |F|≥s^n with distinct coefficient elements.The construction is an explicit MDS array-code family based on the general parity-check framework.
  • MDS property: The construction is MDS, so any k nodes recover the codeword.The MDS claim is established separately from the repair argument.
  • Complexity and updates: The code also has low-complexity encoding and decoding procedures together with the optimal update property.These properties follow from the same diagonal-matrix construction used in the preceding section.
  • Repair: Theorem IV.4 establishes universally error-resilient d-optimal repair for the constructed code.The repair applies to any helper set of size d+2t when at most t helper nodes are erroneous.
  • Error resilience: Repair downloads (d+2t)l/s field symbols from d+2t helpers, while tolerating at most t erroneous helper nodes.The proof uses a length-(n-1), dimension-d Generalized Reed-Solomon code to reconstruct the needed failed-node coordinates.

V. MDS ARRAY CODES WITH THE UER d-OPTIMAL REPAIR PROPERTY FOR SEVERAL VALUES OF d

The paper combines helper-count extensions through a least-common-multiple subpacketization choice, then extends repair from one failure to all h≤r failures. The resulting codes achieve universally error-resilient optimal repair simultaneously across the full allowed h and d ranges.

  • Several helper counts: Replacing the single-helper-count parameter with an lcm lets one construction support several d values simultaneously.For target values d_1,…,d_m, the construction uses s=lcm(d_1+1-k,…,d_m+1-k).
  • Several helper counts: For several selected helper counts, Theorem V.1 establishes UER d_i-optimal repair for all selected d_i simultaneously.The repair downloads (d_i+2t)l/s_i symbols from d_i+2t helpers while tolerating t erroneous helpers.
  • Corollaries: Construction 1 also obtains UER d-optimal repair whenever (d+1-k) divides (n-k).Examples include simultaneous UER (k+1)- and (k+2)-optimal repair for a code with six parity nodes.
  • All erasure counts: Theorem VI.1 gives the UER (h,d)-optimal repair property for every h≤r and k≤d≤n-h.The proof repairs erased nodes sequentially, adding already recovered nodes to the helper set.
  • Complexity: The all-range construction retains optimal updates and restricts encoding and repair to matrices no larger than n×n.These complexity properties follow from the diagonal matrices and the repair proof.

VII. OPTIMAL-REPAIR MDS ARRAY CODES WITH OPTIMAL ACCESS PROPERTY OVER SMALL FIELDS

Construction 4 uses permutation matrices to obtain an explicit MDS array-code family with optimal access over fields of size at least n+1. The code is proved MDS and repairs every node by accessing only designated coordinate subsets from surviving nodes.

  • Construction: Construction 4 sets A_n=I and uses permutation matrices A_1,...,A_{n-1}, reducing the field-size requirement to |F|≥n+1 while obtaining optimal access.The construction has subpacketization l=r^(n−1).
  • Optimal access: Theorem VII.2 establishes that Construction 4 has the optimal access property.
  • Repair: For a failed node C_i with i∈[n−1], repair accesses coordinates satisfying a_i=0 from every surviving node.The parity-check equations determine all coordinates of C_i from these accessed values.
  • Repair: For a failed node C_n, repair accesses coordinates satisfying a_1⊕...⊕a_{n−1}=0 from every surviving node.The same parity-check equations determine the complete failed node from this coordinate subset.
  • MDS property: Construction 4 is an MDS array code because its block matrices commute and every pairwise difference A_i−A_j is invertible.Lemma VII.3 reduces block-Vandermonde invertibility to these pairwise conditions.

A. Complexity of encoding and decoding

Encoding and decoding reduce to solving parity-check equations whose unknowns decompose into independent groups. This replaces one large matrix inversion with many smaller inversions.

  • Procedure: Encoding and decoding determine r unknown nodes from k known nodes using rl equations and rl unknown elements.The MDS property guarantees unique determination.
  • Procedure: For fixed digit values b_1,...,b_k, the unknowns form a group of size r^(r+1) appearing in exactly r^(r+1) equations.Each group can be solved independently.
  • Complexity: The grouped procedure requires inverting r^(r+1)×r^(r+1) matrices instead of one rl×rl matrix.

VIII. EXPLICIT MDS ARRAY CODES WITH THE UER d-OPTIMAL ACCESS PROPERTY

Construction 5 extends the permutation-matrix approach to universally error-resilient d-optimal access. It is MDS, and repair remains possible despite bounded errors among helper nodes.

  • Construction: Construction 5 uses |F|≥n+1 and subpacketization l=sn, with s=d+k−1.
  • MDS property: Construction 5 is an MDS array code because its encoding matrices commute and have invertible pairwise differences.
  • Repair: The code has the UER d-optimal access property.Repair accesses selected coordinate subsets from helper nodes rather than arbitrary linear combinations.
  • Error resilience: The accessed vectors form an (n−1,d,sn−1) MDS array code, enabling recovery from d+2t accessed vectors when at most t helper nodes are erroneous.

IX. AN MDS ARRAY CODE FAMILY WITH THE UER d-OPTIMAL ACCESS PROPERTY FOR SEVERAL VALUES OF d SIMULTANEOUSLY

The paper extends Construction 5 to support several helper-node counts simultaneously and then chooses s=lcm(1,2,...,r) to obtain universal h- and d-optimal access. The resulting Construction 6 is MDS and supports UER repair for all h≤r and k≤d≤n−h.

  • IX. Multiple d values: Replacing s with lcm(d_1+1−k,...,d_m+1−k) supports UER d-optimal access for multiple specified values d_1,...,d_m simultaneously.
  • IX. Multiple d values: Construction 5 provides UER d_i-optimal access for each selected d_i while retaining an MDS array-code structure.
  • X. All h and d: Theorem X.1 gives UER (h,d)-optimal access for every h≤r and k≤d≤n−h simultaneously.
  • X. All h and d: Construction 6 sets s=lcm(1,2,...,r) and l=sn over fields of size at least n+1.
  • X. All h and d: Multiple erased nodes are repaired sequentially, and the accessed-coordinate union has size hl^(d+h−k), matching the repair-bandwidth lower bound.

XI. GENERALIZED REED-SOLOMON ARRAY CODES AND d-OPTIMAL REPAIR PROPERTY

This section introduces a family of MDS array codes with the d-optimal repair property, extending an earlier construction while reducing field-size and sub-packetization requirements.

  • The construction extends Construction 4 to produce MDS array codes with the d-optimal repair property.
  • The family requires a smaller underlying field size than Construction 2.
  • The family uses a smaller l than both Construction 2 and Construction 5.

A. Generalized Reed-Solomon Array Codes

Generalized Reed-Solomon array codes are defined from commuting matrix sets with pairwise invertible differences and compatible invertible matrices, and they retain the MDS property.

  • A Generalized Reed-Solomon array code is defined using commuting matrices Ai whose pairwise differences Ai − Aj are invertible.
  • The code also uses invertible matrices Vi satisfying AiVj = VjAi for every i and j.
  • When all Vi equal the identity matrix, the generalized code is called a Reed-Solomon array code.
  • Generalized Reed-Solomon array codes have the MDS property, and their dual-code description supports subsequent repair arguments.
  • Theorem XI.2 supplies invertible matrices Wi compatible with every Ai for the generalized code.

B. A family of MDS array codes with the d-optimal repair property

This section constructs an MDS array-code family with d-optimal repair using a field of size at least n+1 and proves both its MDS and repair properties.

  • The construction uses a finite field with |F| ≥ n+1, s = d+1−k, and sub-packetization l = s^(n−1).
  • The resulting code is an MDS array code.
  • The resulting code has the d-optimal repair property.
  • Repair recovers a failed node by downloading a vector in F^(l/s) from each helper node.The argument applies the generalized Reed-Solomon representation and uses an invertible transformation of the failed node.

C. Extension to d-optimal repair property for several values of d simultaneously

The construction is extended to support d-optimal repair for several helper counts simultaneously by choosing a shared sub-packetization parameter based on their least common multiple.

  • For helper counts d1, d2, …, dm, the construction replaces s with lcm(d1+1−k, d2+1−k, …, dm+1−k).
  • The resulting (n, k, l = s^(n−1)) MDS array code has di-optimal repair property for all listed i simultaneously.
  • For each di, repair downloads a vector in F^(l/si) from each helper node, where si = di+1−k.
  • Construction 4 has d-optimal repair when d+1−k divides n−k.

XII. CONCLUSION

The paper identifies remaining challenges in constructing explicit high-rate regenerating codes with small fields and subpacketization while retaining optimal repair properties.

  • The constructions use fields whose size is proportional to the code length n.
  • Constructing codes with similar properties over a constant-size field remains an open problem.
  • Reducing the subpacketization value l while preserving the stated properties also remains open.
Loading 1604.00454v2…