pith. sign in

arxiv: 1906.10310 · v1 · pith:5IXF42ZAnew · submitted 2019-06-25 · 💻 cs.IT · math.CO· math.IT

Repairing Generalized Reed-Muller Codes

Tingting Chen , Xiande Zhang This is my paper

Pith reviewed 2026-05-25 16:36 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords generalized reed-muller codesdistributed storagerepair bandwidthlocalitysingle failure repairmultiple failureslinear repair scheme
0
0 comments X

The pith

GRM codes support a generalized linear repair scheme that brings single-failure bandwidth close to the theoretical lower bound for small subfields.

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

The paper extends an optimal linear repair method originally developed for Reed-Solomon codes to Generalized Reed-Muller codes that appear in distributed storage. The extension uses the locality of GRM codes to keep repair bandwidth low for a single erased node and shows this bandwidth approaches the information-theoretic lower bound when the subfield is small. The same construction is then applied to multiple failures under both distributed and centralized repair models, with explicit formulas for expected bandwidth across erasure patterns. A sympathetic reader cares because lower repair bandwidth directly reduces the amount of data that must move across the network during recovery.

Core claim

We generalize Guruswami and Wooters' repairing scheme to GRM codes for single failure, which has nontrivial bandwidth closing to the lower bound when the subfield is small. We further extend the repair scheme for multiple failures in distributed and centralized repair models, and compute the expectation of bandwidth by considering different erasure-patterns.

What carries the argument

The linear repair construction generalized from Reed-Solomon codes using the locality properties of GRM codes.

Load-bearing premise

The locality and algebraic structure of GRM codes allow the Reed-Solomon repair scheme to transfer directly without introducing extra bandwidth overhead.

What would settle it

Compute the exact repair bandwidth for a small explicit GRM code over a small subfield and check whether the measured quantity stays within the claimed distance of the lower bound.

Figures

Figures reproduced from arXiv: 1906.10310 by Tingting Chen, Xiande Zhang.

Figure 1
Figure 1. Figure 1: Mi represent a submatrix of M[I, :] as depicted on the right side, the blank block in the left matrix is zero, and xξ~ is the vector (xξ1, xξ2, · · · , xξt). Consider the polynomial f(x) = Pli u=1 c0x u−1 h ~ξ, y(i,u) i. Since h ~ξ, y(i,r) i 6= 0, we know that f(x) 6= 0, then M[Ii , :] · y =      f(αi1) f(αi2) . . . f(αili )      . If M[Ii , :] · y = 0, then f(x) has li distinct roots αi1, . . . … view at source ↗
Figure 2
Figure 2. Figure 2: For a GRM code over Fq with t = 4, p = 24 , q = p t = 164 , µ = 164 − 163 , m = 2, then s = 2, d = 167 , k = 168 − 167 + 1. And then for 1 ≤ l ≤ 8, l satisfies l ≤ d − 1, there is a trivial upper bound kt. Further, l also satisfies the conditions of Remarks IV.2 and IV.3. For the worst case, the upper bound for both distributed and centralized model is l(q − 1)(t − s). And for the best case, the upper boun… view at source ↗
read the original abstract

In distributed storage systems, both the repair bandwidth and locality are important repair cost metrics to evaluate the performance of a storage code. Recently, Guruswami and Wooters proposed an optimal linear repair scheme based on Reed-Solomon codes for a single failure, improved the bandwidth of the classical repair scheme. In this paper, we consider the repair bandwidth of Generalized Reed-Muller (GRM) codes, which have good locality property. We generalize Guruswami and Wooters' repairing scheme to GRM codes for single failure, which has nontrivial bandwidth closing to the lower bound when the subfield is small. We further extend the repair scheme for multiple failures in distributed and centralized repair models, and compute the expectation of bandwidth by considering different erasure-patterns.

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

Summary. The manuscript generalizes the Guruswami-Wooters linear repair scheme from Reed-Solomon codes to Generalized Reed-Muller (GRM) codes. For single failures it claims a nontrivial repair bandwidth that approaches the lower bound when the subfield is small. The scheme is extended to multiple failures under both distributed and centralized repair models, with the expected bandwidth computed over varying erasure patterns.

Significance. If the claimed generalization holds with explicit constructions that incur no extra overhead beyond the RS case, the result would extend known bandwidth-efficient repair techniques to a family of codes valued for their locality properties. This could be useful for distributed storage applications. The manuscript does not indicate the presence of machine-checked proofs, reproducible code, or parameter-free derivations.

major comments (1)
  1. [Abstract] Abstract: the central claim that the generalized scheme yields nontrivial bandwidth close to the lower bound is asserted without any derivation, error analysis, or explicit construction supplied, so the claim cannot be verified from the given material and may rest on unstated modeling choices.
minor comments (1)
  1. [Abstract] The abstract paragraph on single-failure repair should state the precise conditions (e.g., subfield size relative to code parameters) under which the bandwidth is asserted to approach the lower bound.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the comments on our manuscript. Below we address the major comment point by point. The full paper contains the explicit constructions and derivations referenced in the abstract; we are happy to revise the abstract for clarity if the editor requests.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the generalized scheme yields nontrivial bandwidth close to the lower bound is asserted without any derivation, error analysis, or explicit construction supplied, so the claim cannot be verified from the given material and may rest on unstated modeling choices.

    Authors: The abstract is a summary; the explicit linear repair scheme generalizing Guruswami-Wooters to GRM codes, including the precise construction over the subfield, the bandwidth expression, and its comparison to the information-theoretic lower bound (which approaches the bound as the subfield size decreases), appears in Sections 3 and 4 of the manuscript. The analysis is deterministic and does not rely on unstated modeling choices beyond the standard distributed-storage repair model used in the RS case. We can add parenthetical section references to the abstract in a revision. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a generalization of the external Guruswami-Wooters linear repair scheme (from Reed-Solomon codes) to GRM codes, relying on the locality properties of GRM codes to achieve bandwidth approaching the lower bound for small subfields. The abstract and claims contain no self-definitional steps, no fitted inputs renamed as predictions, and no load-bearing self-citations; the central construction is described as a direct extension of an independent prior result without reducing to quantities defined inside this paper. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that GRM codes admit the same style of linear repair as Reed-Solomon codes once locality is granted; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption GRM codes possess good locality property
    Invoked in the abstract to justify considering GRM codes for the repair problem.

pith-pipeline@v0.9.0 · 5648 in / 1272 out tokens · 37075 ms · 2026-05-25T16:36:59.741727+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 internal anchor

  1. [1]

    Network coding for distributed storage systems,

    A. G. Dimakis, P. B. Godfrey, Y . Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE transactions on information theory, vol. 56, no. 9, pp. 4539–4551, 2010

    work page 2010

  2. [2]

    A survey on network codes for distributed storage,

    A. G. Dimakis, K. Ramchandran, Y . Wu, and C. Suh, “A survey on network codes for distributed storage,” Proceedings of the IEEE , vol. 99, no. 3, pp. 476–489, 2011

    work page 2011

  3. [3]

    Self-repairing homomorphic codes for distributed storage systems,

    F. Oggier and A. Datta, “Self-repairing homomorphic codes for distributed storage systems,” in 2011 Proceedings IEEE INFOCOM . IEEE, 2011, pp. 1215–1223

    work page 2011

  4. [4]

    On the locality of codeword symbols,

    P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” IEEE Transactions on Information Theory , vol. 58, no. 11, pp. 6925–6934, 2012

    work page 2012

  5. [5]

    Locally repairable codes,

    D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” IEEE Transactions on Information Theory , vol. 60, no. 10, pp. 5843–5855, 2014

    work page 2014

  6. [6]

    Polynomial codes over certain finite fields,

    I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” Journal of the society for industrial and applied mathematics , vol. 8, no. 2, pp. 300–304, 1960

    work page 1960

  7. [7]

    Repairing Reed-Solomon codes,

    V . Guruswami and M. Wootters, “Repairing Reed-Solomon codes,” IEEE Transactions on Information Theory , vol. 63, no. 9, pp. 5684–5698, 2017

    work page 2017

  8. [8]

    Repairing Reed-Solomon codes with multiple erasures,

    H. Dau, I. M. Duursma, H. M. Kiah, and O. Milenkovic, “Repairing Reed-Solomon codes with multiple erasures,” IEEE Transactions on Information Theory, vol. 64, no. 10, pp. 6567–6582, 2018

    work page 2018

  9. [9]

    Repairing multiple failures for scalar MDS codes,

    J. Mardia, B. Bartan, and M. Wootters, “Repairing multiple failures for scalar MDS codes,” IEEE Transactions on Information Theory , 2018

    work page 2018

  10. [10]

    Repairing algebraic geometry codes,

    L. Jin, Y . Luo, and C. Xing, “Repairing algebraic geometry codes,” IEEE Transactions on Information Theory , vol. 64, no. 2, pp. 900–908, 2018

    work page 2018

  11. [11]

    Reed–Muller codes achieve capacity on erasure channels,

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. S ¸as ¸o ˇglu, and R. L. Urbanke, “Reed–Muller codes achieve capacity on erasure channels,” IEEE Transactions on information theory , vol. 63, no. 7, pp. 4298–4316, 2017

    work page 2017

  12. [12]

    Reed-Muller Codes Achieve Capacity on the Binary Erasure Channel under MAP Decoding

    S. Kudekar, M. Mondelli, E. S ¸as ¸o˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on the binary erasure channel under MAP decoding,” arXiv preprint arXiv:1505.05831, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  13. [13]

    New generalizations of the Reed-Muller codes–I: Primitive codes,

    T. Kasami, S. Lin, and W. Peterson, “New generalizations of the Reed-Muller codes–I: Primitive codes,” IEEE Transactions on Information Theory , vol. 14, no. 2, pp. 189–199, 1968

    work page 1968

  14. [14]

    On generalized Reed-Muller codes and their relatives,

    P. Delsarte, J.-M. Goethals, and F. J. Mac Williams, “On generalized Reed-Muller codes and their relatives,” Information and control , vol. 16, no. 5, pp. 403–442, 1970

    work page 1970

  15. [15]

    List decoding of q-ary Reed-Muller codes,

    R. Pellikaan and X.-W. Wu, “List decoding of q-ary Reed-Muller codes,” IEEE Transactions on Information Theory , vol. 50, no. 4, pp. 679–682, 2004

    work page 2004

  16. [16]

    Efficient decoding algorithms for generalized Reed-Muller codes,

    K. G. Paterson and A. E. Jones, “Efficient decoding algorithms for generalized Reed-Muller codes,” IEEE Transactions on Communications , vol. 48, no. 8, pp. 1272–1285, 2000. 13

    work page 2000

  17. [17]

    Generalized Reed-Muller codes and power control in OFDM modulation,

    K. G. Paterson, “Generalized Reed-Muller codes and power control in OFDM modulation,” IEEE Transactions on Information Theory , vol. 46, no. 1, pp. 104–120, 2000

    work page 2000

  18. [18]

    Locally decodable codes,

    S. Yekhanin, “Locally decodable codes,” Foundations and Trends® in Theoretical Computer Science , vol. 6, no. 3, pp. 139–255, 2012

    work page 2012

  19. [19]

    On locality in distributed storage systems,

    A. S. Rawat and S. Vishwanath, “On locality in distributed storage systems,” in 2012 IEEE Information Theory Workshop . IEEE, 2012, pp. 497–501

    work page 2012

  20. [20]

    Cooperative local repair in distributed storage,

    A. S. Rawat, A. Mazumdar, and S. Vishwanath, “Cooperative local repair in distributed storage,” EURASIP Journal on Advances in Signal Processing , vol. 2015, no. 1, p. 107, 2015

    work page 2015

  21. [21]

    Maximizing data locality in distributed systems,

    F. Chung, R. Graham, R. Bhagwan, S. Savage, and G. M. V oelker, “Maximizing data locality in distributed systems,” Journal of Computer and System Sciences, vol. 72, no. 8, pp. 1309–1316, 2006

    work page 2006

  22. [22]

    Locality and availability of array codes constructed from subspaces,

    N. Silberstein, T. Etzion, and M. Schwartz, “Locality and availability of array codes constructed from subspaces,” IEEE Transactions on Information Theory, 2018

    work page 2018

  23. [23]

    W. C. Huffman and V . Pless, Fundamentals of error-correcting codes . Cambridge university press, 2010

    work page 2010

  24. [24]

    Lidl and H

    R. Lidl and H. Niederreiter, Finite fields. Cambridge university press, 1997, vol. 20

    work page 1997

  25. [25]

    Optimal repair schemes for some families of full-length Reed-Solomon codes,

    H. Dau and O. Milenkovic, “Optimal repair schemes for some families of full-length Reed-Solomon codes,” in 2017 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2017, pp. 346–350

    work page 2017

  26. [26]

    Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems,

    C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems,” ACM Transactions on Storage (TOS) , vol. 9, no. 1, p. 3, 2013

    work page 2013