Huawei Wu

Huawei Wu

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.

Hai Liu, Huawei Wu

For an $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$, how small can the repair bandwidth and repair I/O be under linear exact repair? We study this question in the regime where the field size $q$, the redundancy $r=n-k$, and the sub-packetization level $\ell$ are fixed, while the code length $n$ varies, and we develop a geometric approach to this setting. Our starting point is an intrinsic reformulation of linear exact repair for MDS array codes in terms of subspace intersections and, for repair I/O, the projective point configurations induced by a parity-check realization. This viewpoint yields a simple projective counting argument establishing the general lower bound $$β_{\mathrm{avg}},β_{\max},γ_{\mathrm{avg}},γ_{\max}\;\ge\;\ell(n-1)-\frac{q^{(r-1)\ell}-1}{q-1}$$ for linear exact repair of every $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$ with redundancy $r=n-k\ge 2$. To our knowledge, this is the first lower bound of this form that applies to arbitrary redundancy $r\ge 2$ and sub-packetization level $\ell$. At first glance, the projective counting bound appears rather coarse and therefore unlikely to be attained. We prove that this intuition is correct whenever $r\ge 3$ and $\ell\ge 2$. For $r=2$, the picture changes completely. Using Desarguesian spreads from finite geometry, we construct MDS array codes that attain the bound over a broad interval of code lengths, up to the maximum possible length $q^{\ell}+1$, and do so simultaneously for both repair bandwidth and repair I/O. In the smallest nontrivial case $(r,\ell)=(2,2)$, we also prove a converse within the regular-spread model. Together, these results identify a uniform obstruction governing linear exact repair and show that, in the two-parity case, this obstruction is tight.

Huawei Wu

We study linear exact repair for $(n,k,\ell)$ MDS array codes over $\mathbb{F}_q$, with redundancy $r=n-k$, in the regime where $q$, $r$, and $\ell$ are fixed and the code length $n$ varies. A recent projective counting argument gives a general lower bound on repair bandwidth and repair I/O in this setting. While this bound is attained over a broad interval of code lengths in the two-parity case, it is not attained once $r\ge 3$ and $\ell\ge 2$. In this paper, we refine the counting argument behind this bound and establish a sharper lower bound, which we call the incidence-multiplicity bound. We prove that for every $(n,k,\ell)$ MDS array code over $\mathbb{F}_q$ with $r\ge 2$, both the average and worst-case repair bandwidth, as well as the average and worst-case repair I/O, are at least $$\ell(n-1)-(r-1)\frac{q^\ell-1}{q-1}.$$This bound agrees with the earlier projective counting bound when $r=2$, and is strictly stronger for every $r\ge 3$. We also show that the incidence-multiplicity bound is sharp in a broad parameter range. Assume that $\ell\ge 2$, $r\ge 2$, $(r-1)\mid(q-1)$, and $(q-1)/(r-1)\ge 2$. Then for every integer $n$ satisfying $$2(r-1)\frac{q^\ell-1}{q-1}\le n\le q^\ell+1,$$ there exists an $(n,n-r,\ell)$ MDS array code over $\mathbb{F}_q$ that attains the incidence-multiplicity bound simultaneously for both repair bandwidth and repair I/O. These codes arise from field reduction of a normal rational curve. Together, these results reveal incidence multiplicity as the governing geometric principle for linear exact repair in MDS array codes beyond the two-parity case.