pith. sign in

arxiv: 1907.08938 · v2 · pith:ZU2J6GBVnew · submitted 2019-07-21 · 💻 cs.IT · math.IT

Multi-Layer Transformed MDS Codes with Optimal Repair Access and Low Sub-Packetization

Hanxu Hou , Patrick P. C. Lee , Yunghsiang S. Han This is my paper

Pith reviewed 2026-05-24 18:35 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords MDS codesoptimal repair accesssub-packetizationdistributed storagearray codesEVENODD codesrepair bandwidth
0
0 comments X

The pith

Multi-layer transformed MDS codes achieve optimal repair access with sub-packetization below the known lower bound.

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

The paper constructs a new family of MDS codes called multi-layer transformed MDS codes for use in distributed storage. These codes ensure optimal repair access for any single failed node, meaning the minimum number of symbols is accessed from d surviving nodes. Their sub-packetization equals (d-k+1) raised to the ceiling of n divided by (d-k+1) times eta, where eta equals the floor of (n-k-1) divided by (d-k). This value is strictly smaller than the prior lower bound of (d-k+1) to the ceiling of n over (d-k+1) whenever eta exceeds 1. The savings arise because each repair is limited to one of several specific sets of d helper nodes rather than any d nodes. The authors also apply the same transformation to EVENODD codes to obtain binary array codes with similar gains in sub-packetization.

Core claim

We propose a class of multi-layer transformed MDS codes such that the sub-packetization is (d-k+1)^⌈n/((d-k+1)η)⌉, where η=⌊(n-k-1)/(d-k)⌋, and the repair access is optimal for any single node. We show that the sub-packetization of the proposed multi-layer transformed MDS codes is strictly less than the existing known lower bound when η>1, achieving by restricting the choice of d specific helper nodes in repairing a failed node. We further propose multi-layer transformed EVENODD codes that have optimal repair access for any single node and lower sub-packetization than the existing binary MDS array codes with optimal repair access for any single node.

What carries the argument

The multi-layer transformation applied to MDS codes, which layers the code structure so that the exponent in the sub-packetization expression shrinks when repair helpers are drawn only from predetermined sets of d nodes.

If this is right

  • The codes preserve the MDS property while delivering optimal single-node repair access.
  • Sub-packetization is strictly smaller than the unrestricted lower bound whenever η>1.
  • The same transformation produces EVENODD-based binary MDS array codes with lower sub-packetization than prior binary constructions.
  • The resulting codes combine low computational complexity with the stated repair and sub-packetization properties.

Where Pith is reading between the lines

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

  • The known lower bound on sub-packetization implicitly assumes any set of d helpers may be chosen for repair.
  • Systems that can enforce preferred helper sets during repair could therefore operate with smaller per-node storage overhead.
  • The layer-construction idea may extend to codes that tolerate multiple simultaneous failures.
  • The restriction on helpers introduces a new explicit tradeoff between node-selection flexibility and sub-packetization size.

Load-bearing premise

Restricting the choice of d specific helper nodes during repair of a failed node is acceptable without degrading overall system availability or requiring changes to node selection logic.

What would settle it

A concrete (n,k,d) instance with η>1 in which every MDS code with optimal repair access under the restricted-helper rule still requires sub-packetization at least as large as (d-k+1)^⌈n/(d-k+1)⌉.

Figures

Figures reproduced from arXiv: 1907.08938 by Hanxu Hou, Patrick P. C. Lee, Yunghsiang S. Han.

Figure 1
Figure 1. Figure 1: The repair procedure of node 1 of the example given in Section II with [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
read the original abstract

An $(n,k)$ maximum distance separable (MDS) code has optimal repair access if the minimum number of symbols accessed from $d$ surviving nodes is achieved, where $k+1\le d\le n-1$. Existing results show that the sub-packetization $\alpha$ of an $(n,k,d)$ high code rate (i.e., $k/n>0.5$) MDS code with optimal repair access is at least $(d-k+1)^{\lceil\frac{n}{d-k+1}\rceil}$. In this paper, we propose a class of multi-layer transformed MDS codes such that the sub-packetization is $(d-k+1)^{\lceil\frac{n}{(d-k+1)\eta}\rceil}$, where $\eta=\lfloor\frac{n-k-1}{d-k}\rfloor$, and the repair access is optimal for any single node. We show that the sub-packetization of the proposed multi-layer transformed MDS codes is strictly less than the existing known lower bound when $\eta=\lfloor\frac{n-k-1}{d-k}\rfloor>1$, achieving by restricting the choice of $d$ specific helper nodes in repairing a failed node. We further propose multi-layer transformed EVENODD codes that have optimal repair access for any single node and lower sub-packetization than the existing binary MDS array codes with optimal repair access for any single node. With our multi-layer transformation, we can design new MDS codes that have the properties of low computational complexity, optimal repair access for any single node, and relatively small sub-packetization, all of which are critical for maintaining the reliability of distributed storage systems.

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

2 major / 1 minor

Summary. The paper proposes a class of multi-layer transformed MDS codes for (n,k) high-rate codes with optimal repair access. The sub-packetization is given as α=(d-k+1)^⌈n/((d-k+1)η)⌉ with η=⌊(n-k-1)/(d-k)⌋, claimed to be strictly smaller than the known lower bound (d-k+1)^⌈n/(d-k+1)⌉ when η>1. This is achieved by restricting the choice of d specific helper nodes when repairing a failed node. The paper also constructs multi-layer transformed EVENODD codes with optimal repair access and lower sub-packetization than prior binary MDS array codes.

Significance. If valid under the restricted-helper model, the construction offers a concrete reduction in sub-packetization for MDS codes while preserving optimal repair bandwidth and access for single-node failures. The multi-layer transformation on existing MDS codes (including EVENODD) could be a practical design tool for distributed storage when helper selection can be constrained.

major comments (2)
  1. [Abstract] Abstract (third paragraph): the claim that sub-packetization is 'strictly less than the existing known lower bound' when η>1 is obtained 'by restricting the choice of d specific helper nodes'. The referenced lower bound applies to MDS codes whose repair works for an arbitrary set of d surviving nodes. The manuscript must explicitly state whether the new codes meet the hypothesis of that bound or operate under a strictly weaker model; without this, the comparison to the bound is not valid and the headline improvement is not established.
  2. [Abstract] The central construction (multi-layer transformation) is described only at the level of the abstract; no explicit definition of the transformation, the resulting parity-check or generator matrix, or the repair procedure appears in the provided text. Without these, it is impossible to verify that the claimed α formula is achieved while maintaining the MDS property and exact repair.
minor comments (1)
  1. [Abstract] Notation for η and the ceiling expression should be introduced with a short sentence explaining the range of parameters for which η>1 holds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the constructive comments. We will revise the manuscript to explicitly clarify the restricted-helper repair model and to ensure the central construction is described at a level that allows verification from the abstract and early sections.

read point-by-point responses

  1. Referee: [Abstract] Abstract (third paragraph): the claim that sub-packetization is 'strictly less than the existing known lower bound' when η>1 is obtained 'by restricting the choice of d specific helper nodes'. The referenced lower bound applies to MDS codes whose repair works for an arbitrary set of d surviving nodes. The manuscript must explicitly state whether the new codes meet the hypothesis of that bound or operate under a strictly weaker model; without this, the comparison to the bound is not valid and the headline improvement is not established.

    Authors: We agree that the distinction must be stated more explicitly. The existing lower bound assumes that repair must succeed for every possible set of d surviving nodes. Our codes achieve the smaller sub-packetization precisely because they restrict repair to specific, predetermined sets of d helpers; they therefore do not satisfy the hypothesis of that bound. We will revise the abstract and introduction to state clearly that the codes operate under this strictly weaker (restricted-helper) model, thereby contextualizing the comparison without claiming to contradict the unrestricted lower bound. revision: yes

  2. Referee: [Abstract] The central construction (multi-layer transformation) is described only at the level of the abstract; no explicit definition of the transformation, the resulting parity-check or generator matrix, or the repair procedure appears in the provided text. Without these, it is impossible to verify that the claimed α formula is achieved while maintaining the MDS property and exact repair.

    Authors: The full manuscript (Sections 3–5) contains the explicit definition of the multi-layer transformation, the resulting parity-check matrices, and the repair procedure that achieves the stated α while preserving the MDS property and exact repair. To address the concern that the abstract alone is insufficient, we will expand the abstract with a concise but explicit high-level description of the transformation and will add a short preliminary subsection that summarizes the key matrix construction and repair steps before the detailed proofs. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper presents an explicit construction of multi-layer transformed MDS codes whose sub-packetization formula is obtained directly from the layering parameters and transformation rules rather than from any fitted parameter or self-referential definition. The abstract and description acknowledge the restricted helper-node selection as the mechanism for the reported sub-packetization reduction, so the comparison to the existing lower bound does not rely on redefining the bound's hypotheses inside the paper. No self-citation is load-bearing for the core claims, and the derivation chain remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim rests on the new multi-layer transformation technique and the helper-node restriction; no explicit free parameters are introduced beyond standard code parameters n, k, d.

axioms (1)
  • domain assumption Standard MDS property that any k nodes recover the full data
    The paper builds directly on existing MDS codes for storage.
invented entities (1)
  • multi-layer transformation no independent evidence
    purpose: To achieve reduced sub-packetization while preserving MDS and optimal repair properties
    New technique introduced to obtain the stated sub-packetization formula

pith-pipeline@v0.9.0 · 5846 in / 1227 out tokens · 36038 ms · 2026-05-24T18:35:47.012254+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Joint Design of Piggyback and Conjugate Transformation Functions for Repair Bandwidth Reduction in Piggybacking Codes

    cs.IT 2026-05 unverdicted novelty 6.0

    Conjugate-piggybacking codes jointly optimize piggyback and conjugate functions to achieve lower repair bandwidth than prior piggybacking designs while preserving the MDS property over moderate field sizes such as F_{2^8}.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [1]

    Availability in Globally Distributed Storage Systems,

    D. Ford, F. Labelle, F. I. Popovici, M. Stokely, V .-A. Truong, L. Barroso, C. Grimes, and S. Quinlan, “Availability in Globally Distributed Storage Systems,” in Proc. of the 9th Usenix Symposium on Operating Systems Design and Implementation , 2010, pp. 1–7

    work page 2010

  2. [2]

    Network Coding for Distributed Storage Systems,

    A. Dimakis, P. Godfrey, Y . Wu, M. Wainwright, and K. Ramchandran, “Network Coding for Distributed Storage Systems,” IEEE Trans. Information Theory , vol. 56, no. 9, pp. 4539–4551, Sep. 2010

    work page 2010

  3. [3]

    Distributed Storage Codes with Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth Tradeoff,

    N. B. Shah, K. V . Rashmi, P. V . Kumar, and K. Ramchandran, “Distributed Storage Codes with Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth Tradeoff,” IEEE Trans. Information Theory , vol. 58, no. 3, pp. 1837–1852, 2012

    work page 2012

  4. [4]

    Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,

    K. V . Rashmi, N. B. Shah, and P. V . Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Information Theory , vol. 57, no. 8, pp. 5227–5239, August 2011

    work page 2011

  5. [5]

    BASIC Codes: Low-Complexity Regenerating Codes for Distributed Storage Systems,

    H. Hou, K. W. Shum, M. Chen, and H. Li, “BASIC Codes: Low-Complexity Regenerating Codes for Distributed Storage Systems,” IEEE Trans. Information Theory , vol. 62, no. 6, pp. 3053–3069, 2016

    work page 2016

  6. [6]

    Exact-Repair MDS Code Construction Using Interference Alignment,

    C. Suh and K. Ramchandran, “Exact-Repair MDS Code Construction Using Interference Alignment,” IEEE Trans. Information Theory, vol. 57, no. 3, pp. 1425–1442, 2011

    work page 2011

  7. [7]

    Zigzag Codes: MDS Array Codes with Optimal Rebuilding,

    I. Tamo, Z. Wang, and J. Bruck, “Zigzag Codes: MDS Array Codes with Optimal Rebuilding,” IEEE Trans. Information Theory, vol. 59, no. 3, pp. 1597–1616, May 2013

    work page 2013

  8. [8]

    A Generic Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems,

    J. Li, X. Tang, and C. Tian, “A Generic Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems,” IEEE Trans. Information Theory , vol. 64, no. 9, pp. 6257–6267, 2018

    work page 2018

  9. [9]

    Minimum Storage Regenerating Codes for All Parameters,

    S. Goparaju, A. Fazeli, and A. Vardy, “Minimum Storage Regenerating Codes for All Parameters,” IEEE Trans. Information Theory, vol. 63, no. 10, pp. 6318–6328, 2017

    work page 2017

  10. [10]

    Explicit Constructions of High-Rate MDS Array Codes with Optimal Repair Bandwidth,

    M. Ye and A. Barg, “Explicit Constructions of High-Rate MDS Array Codes with Optimal Repair Bandwidth,” IEEE Trans. Information Theory, vol. 63, no. 4, pp. 2001–2014, 2017

    work page 2001

  11. [11]

    Explicit Constructions of Optimal-Access MDS Codes with Nearly Optimal Sub-Packetization,

    ——, “Explicit Constructions of Optimal-Access MDS Codes with Nearly Optimal Sub-Packetization,” IEEE Trans. Information Theory, p. 63076317, 2017

    work page 2017

  12. [12]

    A Tight Lower Bound on the Sub-Packetization Level of Optimal-Access MSR and MDS Codes,

    S. Balaji and P. Kumar, “A Tight Lower Bound on the Sub-Packetization Level of Optimal-Access MSR and MDS Codes,” arXiv:1710.05876v1, 2017

    work page arXiv 2017

  13. [13]

    EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures,

    M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures,” IEEE Trans. on Computers , vol. 44, no. 2, pp. 192–202, 1995

    work page 1995

  14. [14]

    The EVENODD Code And Its Generalization,

    M. Blaum, J. Brady, J. Bruck, J. Menon, and A. Vardy, “The EVENODD Code And Its Generalization,” High Performance Mass Storage and Parallel I/O , pp. 187–208, 2001

    work page 2001

  15. [15]

    X-Code: MDS Array Codes with Optimal Encoding,

    L. Xu and J. Bruck, “X-Code: MDS Array Codes with Optimal Encoding,” IEEE Trans. Information Theory , vol. 45, no. 1, pp. 272–276, 1999

    work page 1999

  16. [16]

    Row-Diagonal Parity for Double Disk Failure Correction,

    P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, and S. Sankar, “Row-Diagonal Parity for Double Disk Failure Correction,” in Proceedings of the 3rd USENIX Conference on File and Storage Technologies , 2004, pp. 1–14

    work page 2004

  17. [17]

    A Family of MDS Array Codes with Minimal Number of Encoding Operations,

    M. Blaum, “A Family of MDS Array Codes with Minimal Number of Encoding Operations,” in IEEE Int. Symp. on Inf. Theory, 2006, pp. 2784–2788. July 24, 2019 DRAFT 32

    work page 2006

  18. [18]

    Binary MDS Brray Codes with Optimal Repair,

    H. Hou and P. P. C. Lee, “Binary MDS Brray Codes with Optimal Repair,” IEEE Transactions on Information Theory (under review, arXiv preprint: arXiv:1809.04380) , 2018

    work page arXiv 2018

  19. [19]

    An Improved Decoding Algorithm for Generalized RDP Codes,

    Z. Huang, H. Jiang, and K. Zhou, “An Improved Decoding Algorithm for Generalized RDP Codes,” IEEE Communications Letters, vol. 20, no. 4, pp. 632–635, 2016

    work page 2016

  20. [20]

    A New Construction of EVENODD Codes with Lower Computational Complexity,

    H. Hou and P. P. C. Lee, “A New Construction of EVENODD Codes with Lower Computational Complexity,” IEEE Communications Letters, vol. 22, no. 6, pp. 1120–1123, 2018

    work page 2018

  21. [21]

    A New Construction and an Efficient Decoding Method for Rabin-Like Codes,

    H. Hou and Y . S. Han, “A New Construction and an Efficient Decoding Method for Rabin-Like Codes,” IEEE Trans. Communications, vol. 66, no. 2, pp. 521–533, 2018

    work page 2018

  22. [22]

    A Unified Form of EVENODD and RDP Codes and Their Efficient Decoding,

    H. Hou, Y . S. Han, K. W. Shum, and H. Li, “A Unified Form of EVENODD and RDP Codes and Their Efficient Decoding,” IEEE Trans. Communications , pp. 1–1, 2018

    work page 2018

  23. [23]

    Triple-Fault-Tolerant Binary MDS Array Codes with Asymptotically Optimal Repair,

    H. Hou, P. P. C. Lee, Y . S. Han, and Y . Hu, “Triple-Fault-Tolerant Binary MDS Array Codes with Asymptotically Optimal Repair,” in Proc. IEEE Int. Symp. Inf. Theory , Aachen, June 2017

    work page 2017

  24. [24]

    A Class of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair,

    H. Hou and Y . S. Han, “A Class of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair,” SCIENCE CHINA (Information Sciences) , vol. 61, no. 10, pp. 52–62, 2018

    work page 2018

  25. [25]

    A New Design of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair,

    H. Hou, Y . S. Han, P. P. C. Lee, Y . Hu, and H. Li, “A New Design of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair,” Accepted in IEEE Trans. Information Theory , 2019

    work page 2019

  26. [26]

    A Note on the Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems,

    J. Li and X. Tang, “A Note on the Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems,” arXiv preprint: arXiv:1901.06067v1 , 2019

    work page arXiv 1901

  27. [27]

    Motwani and P

    R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995

    work page 1995

  28. [28]

    MDS Array Codes with Independent Parity Symbols,

    M. Blaum, J. Bruck, and A. Vardy, “MDS Array Codes with Independent Parity Symbols,” IEEE Trans. Information Theory , vol. 42, no. 2, pp. 529–542, 1996

    work page 1996

  29. [29]

    On the MDS Condition of Blaum-Bruck-Vardy Codes With Large Number Parity Columns,

    H. Hou, K. W. Shum, and H. Li, “On the MDS Condition of Blaum-Bruck-Vardy Codes With Large Number Parity Columns,” IEEE Communications Letters , vol. 20, no. 4, pp. 644–647, 2016

    work page 2016

  30. [30]

    An XOR-Based Erasure-Resilient Coding Scheme,

    J. Blomer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and D. Zuckerman, “An XOR-Based Erasure-Resilient Coding Scheme,” Int. Comput. Sci. Inst., Berkeley, CA, USA, Tech. Rep. TR-95-048 , 1995

    work page 1995

  31. [31]

    New Efficient MDS Array Codes for RAID. Part II. Rabin-Like Codes for Tolerating Multiple (≥ 4) Disk Failures,

    G.-L. Feng, R. H. Deng, F. Bao, and J.-C. Shen, “New Efficient MDS Array Codes for RAID. Part II. Rabin-Like Codes for Tolerating Multiple (≥ 4) Disk Failures,” IEEE Trans. on Computers , vol. 54, no. 12, pp. 1473–1483, 2005

    work page 2005

  32. [32]

    Repair-Optimal MDS Array Codes over GF(2),

    E. E. Gad, R. Mateescu, F. Blagojevic, C. Guyot, and Z. Bandic, “Repair-Optimal MDS Array Codes over GF(2),” in Proc. IEEE Int. Symp. Inf. Theory , 2013, pp. 887–891

    work page 2013

  33. [33]

    Opening the Chrysalis: On the Real Repair Performance of MSR Codes,

    L. Pamies-Juarez, F. Blagojevic, R. Mateescu, C. Guyot, E. E. Gad, and Z. Bandic, “Opening the Chrysalis: On the Real Repair Performance of MSR Codes,” in Proc. of USENIX FAST , 2016, pp. 81–94

    work page 2016

  34. [34]

    Clay Codes: Moulding MDS Codes to Yield an MSR Code,

    M. Vajha, V . Ramkumar, B. Puranik, G. Kini, E. Lobo, B. Sasidharan, P. V . Kumar, A. Barg, M. Ye, S. Narayanamurthy, S. Hussain, and S. Nandi, “Clay Codes: Moulding MDS Codes to Yield an MSR Code,” in 16th USENIX Conference on File and Storage Technologies (FAST 18) . Oakland, CA: USENIX Association, 2018, pp. 139–154. [Online]. Available: https://www.us...

    work page 2018