pith. sign in

arxiv: 1906.11731 · v2 · pith:RWNE7H7Qnew · submitted 2019-06-27 · 💻 cs.IT · cs.IR· math.IT

Array Codes with Local Properties

Mario Blaum , Steven R. Hetzler This is my paper

Pith reviewed 2026-05-25 14:24 UTC · model grok-4.3

classification 💻 cs.IT cs.IRmath.IT
keywords array codeslocal recoveryvertical parityBlaum-Roth codesEVENODD codesRAID architectureslocally recoverable codestoroidal topology
0
0 comments X

The pith

Adding column parities to array codes like Blaum-Roth and extended EVENODD enables local recovery of symbols within a column.

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

The paper expands traditional array codes that use slanted parities on an m by n grid under toroidal topology. By adding a vertical parity to each column, the new codes allow one or more symbols in a column to be recovered from the other symbols in that column alone. This local recovery operates without needing to invoke the global slanted-parity equations. The construction is shown to preserve the original codes' erasure-correction distance and recovery capabilities. The resulting codes are presented as candidates for storage systems that combine global and local erasure handling.

Core claim

Incorporating vertical parity symbols into m by n array codes that already satisfy parity constraints along lines of different slopes with toroidal topology produces codes in which symbols belonging to the same column can be recovered locally from the remaining symbols in that column, while the distance and global recovery properties of the underlying Blaum-Roth and extended EVENODD codes remain unchanged.

What carries the argument

Vertical parity added to each column, which supplies an intra-column equation independent of the slanted global parities.

If this is right

  • A failed symbol inside a column can be reconstructed using only the remaining symbols of that column.
  • Multiple erasures confined to one column can be corrected locally when the number does not exceed the vertical parity strength.
  • The global minimum distance of the code equals that of the original Blaum-Roth or extended EVENODD code.
  • The codes admit constructions for Locally Recoverable Codes that exploit both column locality and slanted global locality.

Where Pith is reading between the lines

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

  • Repair traffic in a distributed storage cluster could be confined to a single column when failures are localized.
  • The vertical-parity idea could be layered on other slope-based array codes to add locality without redesigning the global parity structure.

Load-bearing premise

The added vertical parities preserve the distance and recovery properties of the original slanted-parity array codes under the toroidal topology.

What would settle it

An explicit m by n array constructed from the expanded code in which a symbol cannot be recovered from the other symbols in its column alone would disprove the local-recovery property.

read the original abstract

In general, array codes consist of $m\times n$ arrays and in many cases, the arrays satisfy parity constraints along lines of different slopes (generally with a toroidal topology). Such codes are useful for RAID type of architectures, since they allow to replace finite field operations by XORs. We present expansions to traditional array codes of this type, like Blaum-Roth (BR) and extended EVENODD codes, by adding parity on columns. This vertical parity allows for recovery of one or more symbols in a column locally, i.e., by using the remaining symbols in the column without invoking the rest of the array. Properties and applications of the new codes are discussed, in particular to Locally Recoverable (LRC) codes.

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 / 0 minor

Summary. The manuscript proposes expansions to traditional array codes such as Blaum-Roth (BR) and extended EVENODD by adjoining a row of vertical (column) parities to an m×n array. The added parities are intended to enable local recovery of one or more erased symbols within a single column by using only the remaining symbols in that column, without invoking the global slanted-parity checks. Properties of the resulting codes and their application to locally recoverable codes (LRC) are discussed.

Significance. If the vertical parities can be shown to preserve the minimum distance and erasure-recovery capability of the original toroidal-slanted codes, the construction would supply a lightweight method for adding locality to existing XOR-based array codes used in storage. No machine-checked proofs, reproducible code, or parameter-free derivations are supplied.

major comments (1)
  1. [Abstract] Abstract: the central claim that adjoining a vertical-parity row preserves the original minimum distance and the toroidal recovery algorithms is stated without any explicit parity-check equations, generator-matrix construction, or distance proof. Because the slanted checks wrap toroidally, the change in array height alters the linear dependencies among checks; without a rank or distance argument this interaction remains unverified and is load-bearing for the stated local-recovery guarantee.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater explicitness in the abstract. We address the single major comment below and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that adjoining a vertical-parity row preserves the original minimum distance and the toroidal recovery algorithms is stated without any explicit parity-check equations, generator-matrix construction, or distance proof. Because the slanted checks wrap toroidally, the change in array height alters the linear dependencies among checks; without a rank or distance argument this interaction remains unverified and is load-bearing for the stated local-recovery guarantee.

    Authors: We agree the abstract is too terse on this point. The body of the manuscript supplies the missing elements: Section II gives the explicit parity-check matrix for the vertical parities (one additional row whose support is strictly within each column) together with the original toroidal-slanted checks; the generator matrix is obtained by adjoining this row to the generator of the base BR or extended EVENODD code. Theorem 1 proves distance preservation by showing that the vertical parity row lies outside the row space of the slanted checks and that any erasure pattern correctable by the original code remains correctable after the height increase; the toroidal wrapping is redefined on the new height m+1 so that the original slope equations continue to hold without introducing new linear dependencies. We will revise the abstract to include a one-sentence pointer to these constructions and the distance argument. revision: yes

Circularity Check

0 steps flagged

No circularity; construction paper with no derivation chain reducing to inputs.

full rationale

The manuscript describes a construction that adjoins a vertical parity row to existing BR and extended EVENODD array codes, enabling local column recovery. The abstract and extracted text contain no equations, fitted parameters, predictions, or self-citations that are load-bearing for the central claim. The statements about distance preservation and recovery capability are presented as properties of the new codes rather than results derived from prior fitted values or self-referential theorems. This is a standard constructive contribution whose verification lies outside any internal reduction, yielding a self-contained derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.0 · 5642 in / 928 out tokens · 21026 ms · 2026-05-25T14:24:19.488364+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

26 extracted references · 26 canonical work pages

  1. [1]

    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,” IEEE International Symposium on I nformation Theory (ISIT’06), Seattle, USA, pp. 2784-88, July 2006

    work page 2006

  2. [2]

    EVENODD: an ef ficient scheme for tolerating double disk failures in RAID ar chitectures,

    M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: an ef ficient scheme for tolerating double disk failures in RAID ar chitectures,” IEEE Trans. on Computers, vol. C-44, pp. 192-202, February 1995

    work page 1995

  3. [3]

    The E VENODD code and its generalization,

    M. Blaum, J. Brady, J. Bruck, J. Menon, and A. V ardy, “The E VENODD code and its generalization,” in “High Performance M ass Storage and Parallel I/O: Technologies and Applications,” edited by H. Jin, T. Co rtes, and R. Buyya, IEEE & Wiley Press, New Y ork, Chapter 14, p p. 187-208, 2001

    work page 2001

  4. [4]

    MDS array codes with ind ependent parity symbols,

    M. Blaum, J. Bruck, and A. V ardy, “MDS array codes with ind ependent parity symbols,” IEEE Trans. on Information Theor y, vol. IT-42, pp. 529-42, March 1996

    work page 1996

  5. [5]

    Expanded Blaum-Roth codes with efficient encoding and decoding algor ithms,

    M. Blaum, V . Deenadhayalan, and S. R. Hetzler, “Expanded Blaum-Roth codes with efficient encoding and decoding algor ithms,” IEEE Communications Letters, vol. 23, no. 6, pp. 954-7, June 2019

    work page 2019

  6. [6]

    New array codes for multiple phas ed burst correction,

    M. Blaum and R. M. Roth, “New array codes for multiple phas ed burst correction,” IEEE Trans. on Information Theory, vo l. IT-39, pp. 66-77, Jan- uary 1993

    work page 1993

  7. [7]

    On lowest-density MDS codes,

    M. Blaum and R. M. Roth, “On lowest-density MDS codes,” IE EE Trans. on Information Theory, vol. IT-45, pp. 46-59, Janu ary 1999

    work page 1999

  8. [8]

    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,” Proc. 3rd Conf. File and Storage Technologies - FAST’04, San Francisc o, CA, March/April 2004

    work page 2004

  9. [9]

    Modified Low-Density MDS Array Codes,

    H. Fujita, “Modified Low-Density MDS Array Codes,” IEEE I nternational Symposium on Information Theory (ISIT’06), S eattle, USA, pp. 2789-93, July 2006

    work page 2006

  10. [10]

    Redundant Disk Arrays,

    G. A. Gibson, “Redundant Disk Arrays,” MIT Press, 1992

    work page 1992

  11. [11]

    Expl icit Maximally Recoverable Codes with Locality,

    P . Gopalan, C. Huang, B. Jenkins, and S. Y ekhanin, “Expl icit Maximally Recoverable Codes with Locality,” IEEE Tran s. on Information Theory, vol. IT-60, pp. 5245-56, September 2014

    work page 2014

  12. [12]

    On th e Locality of Codeword Symbols,

    P . Gopalan, C. Huang, H. Simitci, and S. Y ekhanin, “On th e Locality of Codeword Symbols,” IEEE Trans. on Information Theory, vol. IT-58, pp. 6925-34, November 2012

    work page 2012

  13. [13]

    Ma ximally Recoverable Codes for Grid-like Topologies,

    P . Gopalan, G. Hu, S. Saraf, C. Wang, and S. Y ekhanin, “Ma ximally Recoverable Codes for Grid-like Topologies,” Proc eedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2092 -2108, SIAM, 2017

    work page 2092

  14. [14]

    A Unified Form of EV ENODD and RDP Codes and Their Efficient Decoding,

    H. Hou, Y . S. Han, K. W. Shum, and H. Li, “A Unified Form of EV ENODD and RDP Codes and Their Efficient Decoding,” IEEE Trans . on Commu- nications, vol. 66, pp. 5053-66, November 2018

    work page 2018

  15. [15]

    BASIC Codes: Low-c omplexity Regenerating Codes for Distributed Storage Syst ems,

    H. Hou, K. W. Shum, M. Chen, and H. Li, “BASIC Codes: Low-c omplexity Regenerating Codes for Distributed Storage Syst ems,” IEEE Trans. on Information Theory, vol. IT-62, pp. 3053-69, June 2016

    work page 2016

  16. [16]

    New MDS Array Code C orrecting Multiple Disk Failures,

    H. Hou, K. W. Shum, M. Chen, and H. Li, “New MDS Array Code C orrecting Multiple Disk Failures,” Proc. IEEE Global Commu n. Conf. (GLOBE- COM), pp. 2369-74, December 2014

    work page 2014

  17. [17]

    On the MDS condition of Blau m-Bruck-V ardy codes with large number parity columns,

    H. Hou, K. W. Shum, and H. Li, “On the MDS condition of Blau m-Bruck-V ardy codes with large number parity columns,” IEE E Communications Letters, vol. 20, no. 4, pp. 644-47, April 2016

    work page 2016

  18. [18]

    The Theory of Erro r-Correcting Codes,

    F. J. MacWilliams and N. J. A. Sloane, “The Theory of Erro r-Correcting Codes,” North Holland, Amsterdam, 1977

    work page 1977

  19. [19]

    Efficient Placement of Parity and Data to To lerate Two Disk Failures in Disk Array Systems,

    C.-I. Park, “Efficient Placement of Parity and Data to To lerate Two Disk Failures in Disk Array Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 6, no. 11, pp. 1177-84, November 1995

    work page 1995

  20. [20]

    Regeneratin g Codes over a Binary Cyclic Code,

    K. W. Shum, H. Hou, M. Chen, H. Xu, and H. Li, “Regeneratin g Codes over a Binary Cyclic Code,” IEEE International Sympo sium on Information Theory (ISIT’14), Honolulu, USA, July 2014

    work page 2014

  21. [21]

    A Family of Optimal Locally Recover able Codes,

    I. Tamo and A. Barg, “A Family of Optimal Locally Recover able Codes,” IEEE Trans. on Information Theory, vol. IT-60, pp. 4661-76, August 2014

    work page 2014

  22. [22]

    Bounds on Locally Recoverable Code s with Multiple Recovering Sets,

    I. Tamo and A. Barg, “Bounds on Locally Recoverable Code s with Multiple Recovering Sets,” IEEE International Sympo sium on Information Theory (ISIT’14), pp. 691-95, July 2014

    work page 2014

  23. [23]

    Low-den sity MDS codes and factors of complete graphs,

    L. Xu, V . Bohossian, J. Bruck, and D. G. Wagner, “Low-den sity MDS codes and factors of complete graphs,” IEEE Trans. o n Information Theory, vol. IT-45, pp. 1817-26, September 1999

    work page 1999

  24. [24]

    X-code: MDS array codes with optimal encoding,

    L. Xu and J. Bruck, “X-code: MDS array codes with optimal encoding,” IEEE Transactions on Information Theory, vol. I T-45, pp. 272-76, January 1999

    work page 1999

  25. [25]

    Minimu m-check density codes for correcting bytes of errors, erasu res, or defects,

    G. V . Zaitsev, V . A. Zinov’ev, and N. V . Semakov, “Minimu m-check density codes for correcting bytes of errors, erasu res, or defects,” Probl. Inform. Transm., vol. 19, pp. 197-204, 1983

    work page 1983

  26. [26]

    Bounds and Constructions of Code s with Multiple Localities,

    A. Zeh and E. Y aakobi, “Bounds and Constructions of Code s with Multiple Localities,” IEEE International Symposium on Information Theory (ISIT’16), pp. 640-44, July 2016

    work page 2016