pith. sign in

arxiv: 2505.24573 · v2 · pith:FUEL7MPXnew · submitted 2025-05-30 · 💻 cs.IT · math.IT

Maximally recoverable codes with locality and availability

Umberto Mart\'inez-Pe\~nas , V. Lalitha This is my paper

Pith reviewed 2026-05-22 02:22 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords locally repairable codesmaximally recoverable codesavailabilityerasure correctionfinite field sizeMSRD codesdistributed storage
0
0 comments X

The pith

Maximally recoverable LRCs with t-availability are built explicitly from MSRD codes and meet the smallest known field sizes for t=1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors generalize locally repairable codes so that groups of t symbols each have N pairwise disjoint repair sets of size r+δ-1 that fix δ-1 erasures locally. This setup recovers classical LRCs when t equals 1 and reduces storage overhead compared with separate availability for each symbol. They define maximally recoverable LRCs as codes that correct every erasure pattern still fixable after the local repairs are applied. For t=1 they characterize all such patterns, give three explicit constructions from MSRD codes that work over the smallest fields in different parameter ranges, and prove that the known lower bound on field size extends to arbitrary t.

Core claim

Maximally recoverable LRCs with locality and availability are those that correct any erasure pattern that remains correctable after accounting for the N disjoint local repair sets per group of t symbols; for t=1 every such pattern is identified and realized by three explicit constructions based on MSRD codes, each attaining the smallest finite-field size in some regime, while the classical lower bound on field size is shown to hold for any t.

What carries the argument

The MR-LRC definition that requires global correction of every erasure pattern still correctable under the locality and availability constraints given by the N disjoint repair sets of size r+δ-1 per t symbols.

If this is right

  • The new codes achieve the same locality and availability with strictly lower storage overhead than classical LRCs.
  • For t=1 the constructions correct every globally correctable erasure pattern under the availability constraints.
  • The minimal field-size lower bound that was known for ordinary MR-LRCs continues to apply for any value of t.
  • Three different MSRD-based constructions cover distinct parameter regimes while keeping the smallest reported field sizes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The t-parameter may allow designers to trade a modest increase in local group size for fewer total redundant symbols in large-scale storage arrays.
  • Because the constructions rely on MSRD codes, further improvements in rank-metric code families could directly lower the field sizes needed here.
  • The characterization of correctable patterns for t=1 supplies a concrete test that future constructions for t greater than 1 must satisfy to claim maximality.

Load-bearing premise

Any erasure pattern that can still be corrected locally after using the N disjoint repair sets must be correctable globally by the code.

What would settle it

An explicit smaller finite field than the three constructions or the extended lower bound, for parameters where the paper claims the sizes are minimal, or an erasure pattern that satisfies the local repair conditions but is not recovered by one of the constructed codes.

Figures

Figures reproduced from arXiv: 2505.24573 by Umberto Mart\'inez-Pe\~nas, V. Lalitha.

Figure 1
Figure 1. Figure 1: On the left, illustration of a codeword in a code as in Definition 1 for [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
read the original abstract

In this work, we introduce maximally recoverable codes with locality and availability. We consider locally repairable codes (LRCs) where certain subsets of $ t $ symbols belong each to $ N $ local repair sets, which are pairwise disjoint after removing the $ t $ symbols, and which are of size $ r+\delta-1 $ and can correct $ \delta-1 $ erasures locally. Classical LRCs with $ N $ disjoint repair sets and LRCs with $ N $-availability are recovered when setting $ t = 1 $ and $ t=\delta-1=1 $, respectively. Allowing $ t > 1 $ enables our codes to reduce the storage overhead for the same locality and availability. In this setting, we define maximally recoverable LRCs (MR-LRCs) as those that can correct any globally correctable erasure pattern given the locality and availability constraints. We then identify a large class of global erasure patterns that can be corrected by such MR-LRCs and prove that they are all the correctable patterns when $ t=1 $. We provide three explicit constructions of LRCs that can correct such erasure patterns (thus MR-LRCs for $ t=1 $), based on MSRD codes, each attaining the smallest finite-field sizes for some parameter regime. Finally, we extend the known lower bound on finite-field sizes from classical MR-LRCs to our setting (for any value of $ t $).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces maximally recoverable locally repairable codes with locality and availability (MR-LRCs). It considers LRCs in which t symbols each belong to N local repair sets of size r+δ-1 that are pairwise disjoint after removing the t symbols and can correct δ-1 erasures locally. Classical LRCs and LRCs with N-availability are recovered as special cases. MR-LRCs are defined as those correcting every erasure pattern that remains globally correctable after accounting for the local constraints. For t=1 the paper identifies a large class of such patterns, proves the class contains all correctable patterns, gives three explicit MSRD-based constructions that correct exactly these patterns (hence are MR-LRCs for t=1) and attain minimal field sizes in certain regimes, and extends the known lower bound on field size to the new setting for arbitrary t.

Significance. If the central claims hold, the work meaningfully generalizes classical MR-LRCs by incorporating availability and shows that t>1 can reduce storage overhead while preserving locality and availability. The three explicit constructions based on MSRD codes that achieve the smallest finite-field sizes for some parameter regimes, together with the extended lower bound, constitute concrete technical progress. Credit is given for the explicit constructions and for the proof that the identified class exhausts all correctable patterns when t=1.

major comments (1)
  1. [section characterizing correctable patterns for t=1] The proof that the identified class of global erasure patterns exhausts all globally correctable patterns for t=1 (the section characterizing correctable patterns and proving exhaustiveness) must explicitly verify that simultaneous local corrections on overlapping global views cannot produce additional uncorrectable patterns. In particular, when t=1 the N repair sets become disjoint only after removing the single erased symbol; the argument should confirm that shared parities or erasures spanning multiple local groups do not create extra patterns that remain locally correctable yet globally uncorrectable. This completeness is load-bearing for the maximality claim and for the assertion that the three constructions are MR-LRCs.
minor comments (2)
  1. [Abstract] The abstract states that each construction attains the smallest field sizes “for some parameter regime” but does not indicate which construction is optimal in which regime; a brief table or sentence mapping regimes to constructions would improve clarity.
  2. [Introduction / preliminaries] Notation for the parameters N, r, δ, and t is introduced in the abstract and used throughout; a short table collecting the parameter definitions and the recovered special cases (classical LRCs and N-availability) would aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive major comment. We address it below and will incorporate clarifications in the revised version.

read point-by-point responses

  1. Referee: [section characterizing correctable patterns for t=1] The proof that the identified class of global erasure patterns exhausts all globally correctable patterns for t=1 (the section characterizing correctable patterns and proving exhaustiveness) must explicitly verify that simultaneous local corrections on overlapping global views cannot produce additional uncorrectable patterns. In particular, when t=1 the N repair sets become disjoint only after removing the single erased symbol; the argument should confirm that shared parities or erasures spanning multiple local groups do not create extra patterns that remain locally correctable yet globally uncorrectable. This completeness is load-bearing for the maximality claim and for the assertion that the three constructions are MR-LRCs.

    Authors: We thank the referee for this observation on the exhaustiveness argument. Our proof establishes that any globally correctable pattern (after local repairs) must belong to the identified class by deriving necessary conditions from the local repair sets and the global parity-check structure. For t=1 the post-removal disjointness of the N sets is used to show that local corrections operate independently on their respective supports, so that any erasure pattern satisfying the local conditions is already captured by our enumeration; patterns involving shared parities or cross-group erasures either fail local correctability or reduce to one of the enumerated cases without introducing new globally uncorrectable configurations. To make this reasoning fully explicit, we will add a short dedicated paragraph (or remark) in the characterizing section that directly addresses simultaneous local corrections on overlapping views and confirms the absence of additional patterns. This clarification does not alter the main claims or constructions but strengthens the presentation of the completeness proof. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent proofs and external MSRD codes

full rationale

The paper defines MR-LRCs via global correctability under given locality/availability constraints, identifies a specific class of erasure patterns, and proves (for t=1) that this class exhausts all globally correctable patterns. It then gives explicit constructions based on MSRD codes (an external notion) that correct exactly this class, thereby achieving MR-LRCs, and extends a known lower bound from prior classical MR-LRC literature. No equation or step reduces a claimed result to a fitted parameter, self-definition, or self-citation chain by construction; the proofs establish the class equivalence and constructibility independently of the target maximality claim.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on standard finite-field arithmetic and the existence of MSRD codes from prior literature; it introduces a new code family definition but no fitted numerical parameters or new physical entities.

axioms (1)
  • standard math MSRD codes exist over finite fields of the sizes stated in the constructions
    Invoked to build the three explicit LRCs that attain minimal field sizes.
invented entities (1)
  • Maximally recoverable LRC with locality and availability (MR-LRC) no independent evidence
    purpose: Code that corrects every globally correctable erasure pattern under the t-symbol shared-repair-set constraints
    New definition introduced to capture the generalized setting; independent evidence is the claimed constructions and proofs.

pith-pipeline@v0.9.0 · 5792 in / 1438 out tokens · 66304 ms · 2026-05-22T02:22:44.847951+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Blaum, J

    M. Blaum, J. L. Hafner, and S. Hetzler. Partial-MDS codes and their application to RAID type of architectures. IEEE Trans. Info. Theory , 59(7):4510–4519, July 2013

    work page 2013

  2. [2]

    H. Cai, Y. Miao, M. Schwartz, and X. Tang. On optimal locally repairable codes with multiple disjoint repair sets. IEEE Trans. Info. Theory, 66(4):2402–2416, 2020

    work page 2020

  3. [3]

    H. Cai, Y. Miao, M. Schwartz, and X. Tang. A construction of maximally recover- able codes with order-optimal field size. IEEE Trans. Info. Theory, 68(1):204–212, 2022

    work page 2022

  4. [4]

    Gopalan, C

    P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin. Explicit maximally recoverable codes with locality. IEEE Trans. Info. Theory, 60(9):5245–5256, Sept 2014

    work page 2014

  5. [5]

    Gopalan, C

    P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin. On the locality of codeword symbols. IEEE Trans. Info. Theory, 58(11):6925–6934, Nov 2012

    work page 2012

  6. [6]

    Gopi and V

    S. Gopi and V. Guruswami. Improved maximally recoverable LRCs using skew polynomials. IEEE Trans. Info. Theory, 68(11):7198–7214, 2022

    work page 2022

  7. [7]

    S. Gopi, V. Guruswami, and S. Yekhanin. Maximally recoverable LRCs: A field size lower bound and constructions for few heavy parities. IEEE Trans. Info. Theory , 66(10):6066–6083, 2020

    work page 2020

  8. [8]

    G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar. Codes with local regen- eration and erasure correction. IEEE Trans. Info. Theory , 60(8):4637–4660, Aug 2014

    work page 2014

  9. [9]

    Lidl and H

    R. Lidl and H. Niederreiter. Finite Fields, volume 20 ofEncyclopedia of Mathematics and its Applications . Addison-Wesley, Amsterdam, 1983

    work page 1983

  10. [10]

    Lu and P

    H.-F. Lu and P. V. Kumar. A unified construction of space–time codes with optimal rate-diversity tradeoff. IEEE Trans. Info. Theory, 51(5):1709–1730, 2005

    work page 2005

  11. [11]

    F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes . North-Holland Mathematical Library, 1983. 28

    work page 1983

  12. [12]

    Mart´ ınez-Pe˜ nas

    U. Mart´ ınez-Pe˜ nas. Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring. J. Algebra, 504:587–612, 2018

    work page 2018

  13. [13]

    Mart´ ınez-Pe˜ nas and F

    U. Mart´ ınez-Pe˜ nas and F. R. Kschischang. Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes. IEEE Trans. Info. Theory , 65(12):7790–7805, 2019

    work page 2019

  14. [14]

    Mart´ ınez-Pe˜ nas, M

    U. Mart´ ınez-Pe˜ nas, M. Shehadeh, and F. R. Kschischang. Codes in the Sum-Rank Metric, Fundamentals and Applications. Foundations and Trends® in Communi- cations and Information Theory , 19(5):814–1031, 2022

    work page 2022

  15. [15]

    R. W. N´ obrega and B. F. Uchˆ oa-Filho. Multishot codes for network coding using rank-metric codes. In Proc. Third IEEE Int. Workshop Wireless Network Coding , pages 1–6, 2010

    work page 2010

  16. [16]

    A. S. Rawat, D. S. Papailiopoulos, A. G. Dimakis, and S. Vishwanath. Locality and availability in distributed storage. IEEE Trans. Info. Theory, 62(8):4481–4493, Aug 2016

    work page 2016

  17. [17]

    Tamo and A

    I. Tamo and A. Barg. A family of optimal locally recoverable codes. IEEE Trans. Info. Theory, 60(8):4661–4676, Aug 2014

    work page 2014

  18. [18]

    Wang and Z

    A. Wang and Z. Zhang. Repair locality with multiple erasure tolerance. IEEE Trans. Info. Theory, 60(11):6979–6987, 2014. 29

    work page 2014