PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal and Dynamic Locally Repairable Codes with Maximal Recoverability via Sum-Rank Codes

Umberto Martínez-Peñas, Frank R. Kschischang

arXiv:1809.11158v2cs.ITmath.IT

TL;DR

LRCs aim to limit repair work while retaining strong global erasure correction, and general MR-LRCs with unequal localities and distances have faced field-size challenges. This paper uses a sum-rank outer code to construct universal, dynamically modifiable MR-LRCs. The construction achieves MR with global fields roughly g^r and supports updates without global recoding.

  • Problem

    General LRC constructions for multiple localities and distances have faced field-size challenges, while MR-LRCs require correcting every erasure pattern allowed by local constraints.

    Source: §I · p. 2

  • Method

    The paper replaces Gabidulin codes with linearized Reed-Solomon codes in an MR-LRC architecture using an MSRD sum-rank outer code.

    Source: §I · pp. 2–3

  • Results

    The construction achieves maximal recoverability with global fields roughly g^r, improving on previous best-known MR-LRCs for unequal localities and on for equal localities when r ≤ h.

    Source: §VIII · p. 29

  • Takeaways & Limitations

    Local codes, localities, file components, and the number of local groups can be modified without global recoding, while hierarchical MR-LRCs can support any type of hierarchy.

    Source: §VIII · p. 29

Abstract

from arXiv · show

Locally repairable codes (LRCs) are considered with equal or unequal localities, local distances and local field sizes. An explicit two-layer architecture with a sum-rank outer code is obtained, having disjoint local groups and achieving maximal recoverability (MR) for all families of local linear codes (MDS or not) simultaneously, up to a specified maximum locality $ r $. Furthermore, the local linear codes (thus the localities, local distances and local fields) can be efficiently and dynamically modified without global recoding or changes in architecture or outer code, while preserving the MR property, easily adapting to new configurations in storage or new hot and cold data. In addition, local groups and file components can be added, removed or updated without global recoding. The construction requires global fields of size roughly $ g^r $, for $ g $ local groups and maximum or specified locality $ r $. For equal localities, these global fields are smaller than those of previous MR-LRCs when $ r \leq h $ (global parities). For unequal localities, they provide an exponential field size reduction on all previous best known MR-LRCs. For bounded localities and a large number of local groups, the global erasure-correction complexity of the given construction is comparable to that of Tamo-Barg codes or Reed-Solomon codes with local replication, while local repair is as efficient as for the Cartesian product of the local codes. Reed-Solomon codes with local replication and Cartesian products are recovered from the given construction when $ r=1 $ and $ h = 0 $, respectively. The given construction can also be adapted to provide hierarchical MR-LRCs for all types of hierarchies and parameters. Finally, subextension subcodes and sum-rank alternant codes are introduced to obtain further exponential field size reductions, at the expense of lower information rates.

I. INTRODUCTION

LRCs seek to combine low-cost local repair with strong global erasure correction, while MR-LRCs impose a stronger recovery guarantee. This work uses sum-rank outer codes to construct flexible MR-LRCs for equal or unequal localities and develops the sum-rank properties that support universal recovery.

I. INTRODUCTION

  • Global fields of roughly g^r yield general MR-LRCs for equal or unequal localities and distances, with quadratic-complexity global erasure correction.For bounded small r and large g, global decoding is comparable to Tamo-Barg codes and Reed-Solomon codes with local replication; local repair matches Cartesian products of local codes.Source: §I · p. 3
  • For unequal localities, the construction gives the first general MR-LRCs whose global field sizes are not exponential in gr; for equal localities, it improves on when r ≤ h.The paper notes that whether r ≤ h or h < r is more desirable depends on the application.Source: §I · p. 3
  • The same architecture and outer code support arbitrary local linear codes up to dimension r, with local changes and updates possible without global recoding.The MR condition and optimal global distance are preserved; local groups and file components can also be added, removed, or updated.Source: §I · p. 3
  • Universality extends to any number of locality layers, including hierarchies with unequal localities and distances.Lower-level codes can repair fewer erasures while contacting fewer nodes and typically using smaller fields.Source: §I · pp. 3–4

A. Sum-rank Codes

  • Sum-rank distance characterizes worst-case global erasure correction after arbitrary local linear recoding on disjoint groups.The paper states that ρ < d_SR(C) is equivalent to recovery after the specified block transformations.Source: A. Sum-rank Codes · pp. 5–6
  • For equal sublengths, an MSRD code requires extension degree m ≥ N/g, and linearized Reed-Solomon codes attain this minimum.The paper identifies this as the smallest possible extension degree for MSRD codes in the equal-sublength case.Source: A. Sum-rank Codes · p. 7

B. Linearized Reed-Solomon Codes

Linearized Reed-Solomon codes provide MSRD outer codes for sum-rank length partitions. They attain the minimum extension degree in the equal-locality case and specialize to Gabidulin or Reed-Solomon codes under stated parameter choices.

B. Linearized Reed-Solomon Codes

  • The construction assumes 1 ≤ g ≤ q − 1 and localities ri no greater than the extension degree m.These constraints ensure the stated sum-rank length bound N ≤ (q − 1)m.Source: B. Linearized Reed-Solomon Codes · p. 7
  • Linearized Reed-Solomon codes are k-dimensional MSRD codes for the sum-rank length partition N = r1 + r2 + · · · + rg.They attain the minimum extension degree when the sublengths are equal.Source: B. Linearized Reed-Solomon Codes · p. 8
  • Linearized Reed-Solomon codes recover Gabidulin codes when g = 1 and Reed-Solomon codes when m = r1 = · · · = rg = 1.The latter parameter choice also recovers Reed-Solomon codes with local replication.Source: B. Linearized Reed-Solomon Codes · p. 8

III. MAIN CONSTRUCTION OF MR-LRCS

The construction combines an outer MSRD code with disjoint local groups to form an LRC, and the resulting global code is maximally recoverable. Its architecture supports equal or unequal localities and local distances.

Locality cases

  • Localities may equal 1, corresponding to replication of the respective symbol, while local distance δi = 1 gives locality without repair.Source: §III · pp. 9–10

Construction 1

  • Construction 1 uses an outer MSRD code over a global field and local codes on disjoint groups to build the global code.The outer code has sum-rank length N = r1 + r2 + · · · + rg; each local code has dimension ri and length ri + δi − 1.Source: §III · pp. 8, 10

Local codes

  • Local MDS codes are typically chosen over fields with qi ≥ ri + δi − 1; when δi = 2, qi = 2 is possible if 2 divides q, enabling XOR repair.Source: §III · p. 11

Maximal recoverability

  • The construction’s global code is maximally recoverable, according to the stated main result.The result identifies the code as having (ri, δi) localities for i = 1, 2, . . . , g.Source: §III · p. 11

Systematic encoding

  • A systematic encoding can distribute uncoded file symbols among local groups, up to each group’s locality, when particular groups must store particular file parts.Source: §III · p. 12

IV. MR-LRCS WITH ANY LOCAL LINEAR CODES

The paper studies disjoint local groups encoded by arbitrary linear codes over subfields and shows that the construction remains maximally recoverable for any choice of local linear codes. This supports partitioning local MDS codes into shorter products to change localities or form hierarchical codes.

Arbitrary local codes

  • Construction 1 gives maximally recoverable codes for any choice of local linear codes on disjoint groups.Source: §IV · p. 12

Applications

  • Partitioning local MDS codes into shorter Cartesian products over smaller fields can support dynamic locality changes or hierarchical MR-LRCs.Source: §IV · p. 12

A. General MR-LRCs and MSRD Codes

The section establishes that an MSRD outer code over the sum-rank partition yields maximal recoverability for arbitrary disjoint local linear codes, including non-MDS codes. It also characterizes correctable erasures and shows how the construction covers arbitrary local codes with bounded locality.

A. General MR-LRCs and MSRD Codes

  • An MSRD outer code corrects every erasure pattern that is information-theoretically correctable for arbitrary disjoint local linear codes.The correctability criterion is that the sum of the ranks of the surviving local generator-matrix restrictions is at least k.Source: A. General MR-LRCs and MSRD Codes · pp. 12, 14
  • The construction’s two-layer architecture represents disjoint local linear codes through local matrices and an outer code, even when the local codes are not MDS.The codes’ parity checks are local, while the outer code supplies global parities.Source: A. General MR-LRCs and MSRD Codes · pp. 12–13
  • Any erasure pattern correctable by a local code remains correctable globally with the same complexity over the same field.This consequence applies group by group to the local codes.Source: A. General MR-LRCs and MSRD Codes · p. 13
  • The general MR condition specializes to the usual locality-and-distance definition when each local code is MDS.The two definitions are equivalent for local (r_i + δ_i − 1, r_i) MDS codes.Source: A. General MR-LRCs and MSRD Codes · p. 14
  • For arbitrary local linear codes of dimensions at most r, Construction 1 gives MR-LRCs over F_q^m when q > g and m ≥ max_i r_i.The section states that m = r is the smallest extension degree supporting arbitrary local codes up to locality r.Source: A. General MR-LRCs and MSRD Codes · p. 15
  • With no global parities, the construction recovers Cartesian products; with r = 1, it recovers Reed-Solomon global codes with local replication.For h = 0, the outer code can be the whole space; for r = 1, the sum-rank metric becomes Hamming.Source: A. General MR-LRCs and MSRD Codes · p. 15

B. Global Distances and Thresholds for Erasure Correction

This section gives a formula for the global distance of the construction and relates it to maximal recoverability. It establishes the distance result without requiring an ordering of localities and local distances used in earlier studies.

B. Global Distances and Thresholds for Erasure Correction

  • The section supplies a formula for the global distance that applies without assuming r_1 ≤ r_2 ≤ … ≤ r_g or δ_1 ≥ δ_2 ≥ … ≥ δ_g.The authors contrast this with, and earlier studies.Source: B. Global Distances and Thresholds for… · p. 15
  • The construction has global distance d_H(Cglob) = e(A, k) + 1 when it is MR-LRC, and also when its outer code is MSRD.The stated result does not require the locality and local-distance orderings used in earlier studies.Source: B. Global Distances and Thresholds for… · pp. 15–16
  • For ordered MDS local codes, the formula specializes to the earlier results in [19], [20], [17], [18], [6], and [3].The stated specializations cover disjoint local groups, including the equal-locality case.Source: B. Global Distances and Thresholds for… · p. 16

V. UNIVERSAL AND DYNAMIC PROPERTIES

The section describes adaptations of Construction 1 for changing local codes and for modifying the grouping or contents of the stored data. It also covers multi-layer and hierarchical MR-LRCs.

V. UNIVERSAL AND DYNAMIC PROPERTIES

  • Construction 1 supports local recodings, locality partitioning, and multi-layer or hierarchical MR-LRCs.The section treats these as separate adaptation capabilities.Source: §V · p. 17
  • The construction can be used to change the initial localities and the number of local groups.These modifications are included among the section’s supported operations.Source: §V · p. 17
  • The section also considers adding, removing, or updating file components through changes to the construction.The section lists file-component changes alongside changes to localities and group count.Source: §V · p. 17

A. Arbitrary and Efficient Local Linear Recodings

Local linear codes can be changed through operations confined to their groups, while the outer code remains unchanged. When that outer code is MSRD, the MR property is preserved without global recoding.

A. Arbitrary and Efficient Local Linear Recodings

  • Any local linear code can be changed to another by linear operations within its group over the local field, leaving the outer code unchanged.When the outer code is MSRD, the MR condition is preserved, so global recoding is unnecessary.Source: A. Arbitrary and Efficient Local… · p. 17
  • Block-diagonal recoding lets local groups recode stored data without inter-group communication or changes to the outer code.The passage describes these as local operations over the local fields.Source: A. Arbitrary and Efficient Local… · p. 18
  • In the example, one group can be repartitioned into two (4, 3) MDS codes over F2 for faster local repair, while the other groups remain unchanged.The transition is performed locally instead of globally recoding all seven groups over F2^18.Source: A. Arbitrary and Efficient Local… · p. 18

B. Partitioning Local Groups and Initial Localities

The paper shows how sum-rank codes support finer locality partitions and extend the construction to arbitrary hierarchical MR-LRCs. Localities, file components, and group counts can also be changed without global recoding, subject to the stated dimension constraint.

B. Partitioning Local Groups and Initial Localities

  • Locality partitions can be implemented by efficient local linear recoding, and MSRD codes for a coarser sum-rank partition remain MSRD for finer partitions.The partitioning argument also recovers the rank-distance bound by Hamming distance when g = 1 and g1 = N.Source: B. Partitioning Local Groups and… · p. 19

C. Multi-layer or hierarchical MR-LRCs

  • A hierarchical MR-LRC is specified by a rooted tree, parity counts at its vertices, and localities at its leaves; each vertex code must correct all erasure patterns allowed by its local constraints.An internal vertex acts as both a local and global code.Source: C. Multi-layer or hierarchical MR-LRCs · pp. 20–21
  • The construction yields hierarchical MR-LRCs for arbitrary rooted trees, leaf localities, and vertex parities, with a recursively specified global field.Each non-leaf vertex uses a tailored linearized Reed-Solomon code, while the leaves use short MDS codes.Source: C. Multi-layer or hierarchical MR-LRCs · p. 21
  • Initial localities, file size, and the number of local groups can be modified without global recoding, and the three changes can be performed sequentially in any order.The dimension must remain at most the sum of the localities.Source: D. Recursive Encoding, and Changes of… · pp. 22–23
  • Reversible updates let a storage system add or remove groups and file components over time without global recoding.The paper motivates this for incrementally preparing a distributed storage system toward a final file size.Source: D. Recursive Encoding, and Changes of… · p. 22

VI. COMPARISONS BETWEEN DIFFERENT OPTIMAL AND/OR MR-LRCS FOR GENERAL PARAMETERS

The comparison section evaluates global field sizes and local and global erasure-correction costs across the construction and codes from the literature. It does not assess minimum per-node storage.

VI. COMPARISONS BETWEEN DIFFERENT OPTIMAL AND/OR MR-LRCS FOR GENERAL PARAMETERS

  • The comparison covers global field sizes and local and global erasure-correction complexity for the construction and general-parameter codes from the literature.The comparison includes Tamo-Barg codes, Gabrys et al., and Gabidulin-based LRCs,,,.Source: §VI · p. 23
  • The comparison treats the codes’ field-size and decoding costs, rather than providing a minimum-storage analysis.The stated storage scope is bounded by at most linear bits per symbol in gr.Source: §VI · pp. 23–24
  • Minimum per-node storage is not studied because the compared schemes require at most linearly many bits per symbol in gr.The authors state that this storage complexity is not large enough to pose problems in large-scale distributed storage systems.Source: §VI · p. 24

A. Smallest Global Field for given Initial Localities among Linearized Reed-Solomon Codes

For equal initial localities, the finest sum-rank length partition minimizes the global field size among the considered linearized Reed-Solomon choices. The authors illustrate the field-size function and show that nontrivial partition choices improve on Gabidulin’s requirement.

A. Smallest Global Field for given Initial Localities among Linearized Reed-Solomon Codes

  • The finest partition, N = gr, gives the smallest global field size for equal initial localities among linearized Reed-Solomon codes.Although the smallest exponent is r, finer partitions increase the field-size base; the analysis finds the finest partition minimizes the overall field size.Source: A. Smallest Global Field for given… · pp. 24–25
  • For g = 31, r = 6, and δ = 3, Fig. 8 gives F(1) = 2558 for Gabidulin and F(31) = 230 for linearized Reed-Solomon.The figure plots F(x) for x = 1, 2, …, 31 on a base-2 logarithmic y-axis.Source: Figure 8 · p. 24
  • For g ≥ 2, every choice x ≥ 2 reduces the global field size required by Gabidulin codes without loss in performance.The paper identifies x = 1 as the Gabidulin case.Source: A. Smallest Global Field for given… · pp. 24–25

B. Comparison with other MR-LRCs from the Literature

The comparison finds that the construction offers competitive field sizes and decoding costs under stated parameter conditions. The paper also introduces subextension subcodes and sum-rank alternant codes for further field-size reduction, with an information-rate trade-off.

B. Comparison with other MR-LRCs from the Literature

  • Construction 1 has more efficient global decoding than when r ≤ h, while local repair is similar to and Gabidulin-based LRCs.Local repair is more efficient than Tamo-Barg codes, whose global decoding is more efficient.Source: B. Comparison with other MR-LRCs from… · p. 27
  • When g is much larger than r or r is constant, the construction and Tamo-Barg global decoding costs are both O(n^2 log(n)^2) over F2.Gabidulin-based LRCs require O(n^4), while codes in require O(h^2n^2 log(n)^2) in this regime.Source: B. Comparison with other MR-LRCs from… · p. 27
  • For r = 9, δ = 2, and h = g, the construction’s global field size is roughly g^9, compared with g^(n/10) for.In this example, the construction also has O(n^2 log(n)^2) global decoding and local repair by XORing.Source: B. Comparison with other MR-LRCs from… · p. 27

VII. FURTHER FIELD SIZE REDUCTIONS: SUBEXTENSION SUBCODES AND SUM-RANK ALTERNANT CODES

  • Subextension subcodes inherit the original code’s minimum sum-rank distance, and applying them to linearized Reed-Solomon codes yields sum-rank alternant codes.The subextension construction plays the role of subfield subcodes for the Hamming metric.Source: §VII · pp. 27–28
  • The further field-size reduction is exponential with exponent s, at the cost of reducing stored-file entropy by at most (s − 1)(δ* − 1).The authors note that this rate reduction is only bounded and call for sharper lower bounds on subextension-subcode dimension.Source: §VII · p. 29

VIII. CONCLUSION

The proposed architecture achieves maximal recoverability with smaller global fields, while retaining flexibility to change local codes and groups without global recoding. It also supports hierarchical constructions and further field-size reductions at a rate cost.

VIII. CONCLUSION

  • Construction 1 achieves maximal recoverability with global field sizes roughly g^r, improving known fields for equal localities when r ≤ h and for unequal localities over previous best-known constructions.The comparison for equal localities is to the smallest known global fields; for unequal localities, it is to all previous best-known MR-LRCs.Source: §VIII · p. 29
  • Local linear codes, localities, distances, fields, file components, and the number of local groups can be changed without global recoding.The architecture also permits partitioning initial localities without global recoding.Source: §VIII · p. 29
  • The architecture yields explicit multi-layer or hierarchical MR-LRCs for any type of hierarchy and any choice of equal or unequal localities and local distances.Source: §VIII · p. 29
  • Subextension subcodes and sum-rank alternant codes can further reduce global field sizes exponentially, at the cost of lower information rates.Source: §VIII · p. 30

Related papers

Loading 1809.11158v2…