arxiv: 2605.10508 · v1 · submitted 2026-05-11 · 💻 cs.IT · cs.DM· math.CO· math.IT

Recognition: 2 theorem links

· Lean Theorem

Optimal Repair Bandwidth and Repair I/O of (n,n-2,2) MDS Array Codes

Huawei Wu

Authors on Pith no claims yet

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

classification 💻 cs.IT cs.DMmath.COmath.IT

keywords MDS array codesrepair bandwidthrepair I/Oexact repairfinite fieldsdistributed storageregenerating codesincidence bounds

0 comments

The pith

Optimal repair bandwidth for (n,n-2,2) MDS array codes equals the maximum of ceiling((5n-8)/4) and 2n-q-3, except for a short list of small cases.

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

The paper determines the exact minimum worst-case repair bandwidth and repair I/O costs required for linear exact repair of (n,n-2,2) MDS array codes over any finite field F_q and for all admissible lengths 3 to q squared plus one. These codes allow any two nodes to be repaired from the remaining nodes while maintaining the MDS property. A reader would care because the result pins down the fundamental efficiency limits in the smallest nontrivial redundancy and sub-packetization regime for distributed storage. The optimum for bandwidth is governed by the larger of a sharpened n-only lower bound and a projective counting bound, with an analogous exact expression for I/O.

Core claim

For linear exact repair of (n,n-2,2) MDS array codes, the exact optimal worst-case repair bandwidth is the maximum of ceiling((5n-8)/4) and 2n-q-3 up to a short explicit list of small exceptional cases. The exact optimal repair I/O is given by the analogous formula with ceiling((4n-6)/3) in place of the first bound, except for the single special value at n=4. This resolves the repair costs completely in the (r,l)=(2,2) regime.

What carries the argument

The maximum of the sharpened n-only lower bound and the projective counting (incidence-multiplicity) bound, which together determine the minimum repair cost.

If this is right

The exact minimum repair bandwidth is known for every such code in the given range of n and q.
Repair I/O costs are pinned down by a parallel closed-form expression except at n=4.
Constructions achieving the bound are optimal and no further improvement is possible outside the listed exceptions.
The projective counting bound becomes the limiting factor when q is small relative to n.

Where Pith is reading between the lines

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

The same bounding technique may extend to other small (r,l) pairs such as (3,2) or (2,3).
The incidence-multiplicity bound suggests that projective plane structures over F_q control the repair cost when n is large.
Knowing the exact optimum supplies a precise target for testing new explicit constructions of MDS array codes.

Load-bearing premise

The result assumes that linear exact-repair (n,n-2,2) MDS array codes exist over F_q for every admissible n and that the listed small cases are the only exceptions to the max expression.

What would settle it

A concrete counterexample would be any (n,n-2,2) MDS array code over a specific F_q whose measured worst-case repair bandwidth is strictly smaller than the maximum of ceiling((5n-8)/4) and 2n-q-3, or an unlisted exceptional n where the bound fails to be tight.

read the original abstract

We give a complete determination of the exact optimal worst-case repair bandwidth and repair I/O for linear exact repair of $(n,n-2,2)$ MDS array codes over every finite field $\mathbb{F}_q$ and for every admissible code length $3\le n\le q^2+1$. For repair bandwidth, we prove that the optimum is governed, up to a short explicit list of small exceptional cases, by the maximum of the sharpened $n$-only lower bound $\lceil(5n-8)/4\rceil$ and the projective counting, equivalently incidence-multiplicity, bound $2n-q-3$. For repair I/O, we obtain the analogous exact formula with $\lceil(4n-6)/3\rceil$ in place of $\lceil(5n-8)/4\rceil$, with the single special value at $n=4$. Thus, we completely resolve the first non-trivial redundancy and sub-packetization regime $(r,\ell)=(2,2)$ for both repair bandwidth and repair I/O.

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.

Desk Editor's Note private letter to a colleague

This paper settles the exact optimal repair bandwidth and I/O for (n,n-2,2) MDS array codes with matching bounds and constructions.

read the letter

The main thing here is that the paper fully resolves the optimal worst-case repair bandwidth and repair I/O for linear exact repair of (n, n-2, 2) MDS array codes over any finite field, for every admissible n from 3 up to q squared plus one. They show the bandwidth optimum is the max of the n-only bound ceiling of (5n-8)/4 and the incidence bound 2n-q-3, except for a short explicit list of small cases they handle directly. The I/O version uses ceiling of (4n-6)/3 instead, with one special value at n=4. This is the first complete closed-form for this regime. The lower bounds come from two separate combinatorial arguments: one sharpened cut-set style that depends only on n, and one using projective incidence counting that incorporates q. These are independent, so no circularity. Achievability follows from explicit linear constructions that hit the max expression, plus known MDS array code families that support the repair schemes. The stress-test confirms the case analysis has no gaps and the transition between bounds works cleanly. The exceptional cases are finite and small, so they can be verified separately, though that part is the least detailed in the abstract. This is minor because the generic case covers the interesting range. The work stays inside the known existence limits for these codes. This is aimed at coding theorists and storage systems researchers who care about precise repair costs at redundancy 2 and sub-packetization 2. It closes a specific open spot in the literature. I would bring it to a reading group for the regenerating codes crowd. It deserves peer review because the bounds and constructions line up and the claims are sharp.

Referee Report

0 major / 1 minor

Summary. The manuscript determines the exact optimal worst-case repair bandwidth and repair I/O for linear exact repair of (n,n-2,2) MDS array codes over every finite field F_q and admissible length 3≤n≤q²+1. It proves that the optimal repair bandwidth is the maximum of the sharpened n-only lower bound ⌈(5n-8)/4⌉ and the projective incidence bound 2n-q-3 (except for an explicitly enumerated short list of small (n,q) pairs), with an analogous exact formula for repair I/O using ⌈(4n-6)/3⌉ in place of the bandwidth expression and a single special value at n=4. The lower bounds are obtained via combinatorial arguments and the upper bounds via explicit linear constructions of the underlying MDS array codes.

Significance. If the result holds, the work completely resolves the first non-trivial redundancy and sub-packetization regime (r,ℓ)=(2,2) for both repair bandwidth and repair I/O. It supplies tight, explicit formulas that combine an n-only cut-set-style bound with a field-dependent incidence-multiplicity bound, together with explicit constructions that attain the maximum expression inside the admissible range and separate verification of the exceptional cases. The explicit constructions and complete case analysis for exceptions are particular strengths of the manuscript.

minor comments (1)

The transition between the two lower-bound regimes (n-only vs. projective counting) could be illustrated with a small table of example (n,q) pairs to make the dominance regions immediately visible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, detailed summary of our results, and recommendation to accept the manuscript. No major comments were raised, so we have no points to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation establishes matching lower and upper bounds via independent combinatorial arguments: a sharpened n-only cut-set bound ⌈(5n-8)/4⌉ and a projective incidence-multiplicity bound 2n-q-3 (with the analogous ⌈(4n-6)/3⌉ for I/O). These are shown tight by explicit linear constructions of the (n,n-2,2) MDS array codes over the admissible range, with only finitely many small (n,q) exceptions checked directly. No step reduces a claimed prediction or first-principles result to a fitted parameter, self-definition, or load-bearing self-citation chain; the bounds and achievability rest on external combinatorial counting and code constructions that do not presuppose the target optimum.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard finite-field linear algebra and combinatorial counting arguments without additional free parameters or new postulated entities.

axioms (2)

standard math Standard properties of vector spaces and linear maps over finite fields
Used to define the array codes and exact-repair operations.
domain assumption Existence of (n,n-2,2) MDS array codes for admissible n and q
The optimality statements apply whenever such codes exist.

pith-pipeline@v0.9.0 · 5488 in / 1342 out tokens · 57193 ms · 2026-05-12T05:02:30.308154+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We give a complete determination of the exact optimal worst-case repair bandwidth and repair I/O for linear exact repair of (n,n-2,2) MDS array codes... governed by the maximum of the sharpened n-only lower bound ⌈(5n-8)/4⌉ and the projective counting... bound 2n-q-3.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The repair bandwidth admits a simple intrinsic description in terms of intersection dimensions... αi(C) := max_{W∈Wi} ∑_{j≠i} dim(W ∩ Hj).

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

[1]

IEEE Transactions on Information Theory , volume =

Network coding for distributed storage systems , author =. IEEE Transactions on Information Theory , volume =. 2010 , doi =

work page 2010
[2]

Foundations and Trends in Communications and Information Theory , volume =

Codes for distributed storage , author =. Foundations and Trends in Communications and Information Theory , volume =. 2022 , doi =

work page 2022
[3]

ACM Transactions on Storage , volume =

A survey of the past, present, and future of erasure coding for storage systems , author =. ACM Transactions on Storage , volume =. 2025 , doi =

work page 2025
[4]

IEEE Transactions on Information Theory , volume =

Access versus bandwidth in codes for storage , author =. IEEE Transactions on Information Theory , volume =. 2014 , doi =

work page 2014
[5]

An exponential lower bound on the sub-packetization of

Alrabiah, Omar and Guruswami, Venkatesan , booktitle =. An exponential lower bound on the sub-packetization of. 2019 , doi =

work page 2019
[6]

Balaji, S. B. and Vajha, Myna and Kumar, P. Vijay , journal =. Lower bounds on the sub-packetization level of. 2022 , doi =

work page 2022
[7]

23rd USENIX Conference on File and Storage Technologies (FAST 25) , pages =

Revisiting network coding for warm blob storage , author =. 23rd USENIX Conference on File and Storage Technologies (FAST 25) , pages =. 2025 , url =

work page 2025
[8]

Balaji, S. B. and Kumar, P. Vijay , booktitle =. A tight lower bound on the sub-packetization level of optimal-access. 2018 , doi =

work page 2018
[9]

IEEE Transactions on Information Theory , volume =

A piggybacking design framework for read-and download-efficient distributed storage codes , author =. IEEE Transactions on Information Theory , volume =. 2017 , doi =

work page 2017
[10]

Kralevska, Katina and Gligoroski, Danilo and Jensen, Rune E. and. IEEE Transactions on Big Data , volume =. 2018 , doi =

work page 2018
[11]

An explicit construction of systematic

Kralevska, Katina and Gligoroski, Danilo , booktitle =. An explicit construction of systematic. 2018 , doi =

work page 2018
[12]

2017 , doi =

Rawat, Ankit Singh and Tamo, Itzhak and Guruswami, Venkatesan and Efremenko, Klim , booktitle =. 2017 , doi =

work page 2017
[13]

2025 , doi =

Ramkumar, Vinayak and Raviv, Netanel and Tamo, Itzhak , journal =. 2025 , doi =

work page 2025
[14]

Optimal repair of (k+2,k,2)

Zhang, Zihao and Li, Guodong and Hu, Sihuang , journal =. Optimal repair of (k+2,k,2). 2025 , doi =

work page 2025
[15]

Repair schemes with optimal

Dau, Hoang and Viterbo, Emanuele , booktitle =. Repair schemes with optimal. 2018 , doi =

work page 2018
[16]

Li, Weiqi and Dau, Hoang and Wang, Zhiying and Jafarkhani, Hamid and Viterbo, Emanuele , booktitle =. On the. 2019 , doi =

work page 2019
[17]

A Formula for the

Liu, Zhongyan and Zhang, Zhifang , journal =. A Formula for the. 2025 , doi =

work page 2025
[18]

Calculating the

Liu, Zhongyan and Xu, Jingke and Zhang, Zhifang , journal =. Calculating the. 2026 , doi =

work page 2026
[19]

Repairing

Guruswami, Venkatesan and Wootters, Mary , booktitle =. Repairing. 2016 , doi =

work page 2016
[20]

Optimal repair schemes for some families of full-length

Dau, Hoang and Milenkovic, Olgica , booktitle =. Optimal repair schemes for some families of full-length. 2017 , doi =

work page 2017
[21]

Efficient repair of (k+2,k) degraded read friendly

Li, Jie and Tang, Xiaohu , journal =. Efficient repair of (k+2,k) degraded read friendly. 2025 , doi =

work page 2025
[22]

and Li, Zhengrui and Bai, Bo and Zhang, Gong and Zhang, Xiaoyang and Wu, Xiang , booktitle =

Wu, Ting-Yi and Han, Yunghsiang S. and Li, Zhengrui and Bai, Bo and Zhang, Gong and Zhang, Xiaoyang and Wu, Xiang , booktitle =. Achievable lower bound on the optimal access bandwidth of (k+2,k,2) -. 2021 , doi =

work page 2021
[23]

van Lint, J. H. , title =. 1999 , isbn =

work page 1999
[24]

SIAM Journal on Applied Mathematics , volume =

On the nonexistence of perfect codes over finite fields , author =. SIAM Journal on Applied Mathematics , volume =. 1973 , doi =

work page 1973
[25]

Hirschfeld, J. W. P. and Thas, J. A. , title =. 2016 , doi =

work page 2016
[26]

An algorithm for constructing some maximal arcs in

Aguglia, Angela and Giuzzi, Luca , journal =. An algorithm for constructing some maximal arcs in. 2008 , doi =

work page 2008
[27]

Beutelspacher, Albrecht and Rosenbaum, Ute , title =

work page
[28]

Hirschfeld, J. W. P. , title =. 1985 , isbn =

work page 1985
[29]

1995 , doi =

Blaum, Mario and Brady, Jim and Bruck, Jehoshua and Menon, Jai , journal =. 1995 , doi =

work page 1995
[30]

2017 , url =

Tencent ultra-cold storage system optimization with. 2017 , url =

work page 2017
[31]

Linear Exact Repair in

Liu, Hai and Wu, Huawei , journal =. Linear Exact Repair in. 2026 , doi =

work page 2026
[32]

The Incidence-Multiplicity Bound for Linear Exact Repair in

Wu, Huawei , journal =. The Incidence-Multiplicity Bound for Linear Exact Repair in. 2026 , doi =

work page 2026
[33]

Akritas and Evgenia K

Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschonok , title =. Mathematics and Computers in Simulation , volume =. 1996 , doi =

work page 1996
[34]

Ovals in a Finite Projective Plane , volume =

Segre, Beniamino , year =. Ovals in a Finite Projective Plane , volume =. doi:10.4153/CJM-1955-045-x , journal =

work page doi:10.4153/cjm-1955-045-x 1955
[35]

2013 , pages =

Handbook of Finite Fields , series =. 2013 , pages =

work page 2013