Source-linked AI summary
From Linear Exact Repair to Mixed-Alphabet Codes: The Bandwidth-Subpacketization Tradeoff of MDS Array Codes
Zihao Zhang, Guodong Li, Sihuang Hu
TL;DR
For centralized linear exact repair at fixed sub-packetization, the paper studies lower bounds on local repair bandwidth. It reduces repair schemes to auxiliary mixed-alphabet codes and applies classical coding bounds to constrain feasible bandwidth profiles.
Problem
Fixed-sub-packetization lower bounds are needed to study local repair bandwidth for centralized linear exact repair.
Source: §1 · pp. 1–2Method
The paper reduces linear repair schemes to null-space codes for all repair degrees and row-space codes when d ≥ r, then applies classical coding bounds.
Source: §6 · p. 19Results
Singleton, Hamming, Plotkin, and Griesmer arguments yield finite-parameter constraints on feasible bandwidth profiles.
Source: §6 · p. 19Takeaways & Limitations
The auxiliary-code reduction provides a route from classical coding-theoretic bounds to local repair-bandwidth constraints.
Source: §6 · p. 19The row-space auxiliary-code argument requires d ≥ r, while the null-space code applies for all repair degrees.
Source: §3.2 · p. 7, §6 · p. 19
Abstract
from arXiv · showhide
MDS array codes achieve optimal storage efficiency in distributed storage systems, but their repair bandwidth depends critically on the sub-packetization level. While the theoretically optimal repair bandwidth (i.e., cut-set bound) of a high-rate exact-repair MDS array code is attainable with sufficiently large sub-packetization, the fundamental limits for fixed sub-packetization remain poorly understood. We study this problem for centralized linear exact repair of $h$ failures from $d$ helper nodes over a fixed finite field. We show that the rank profile of any linear repair scheme is constrained by two auxiliary mixed-alphabet codes. The first code is formed from the kernels of the helper projections and exists for all repair degrees; the second is formed from their row spaces and applies in the full-helper regime when $d\ge r$. These codes have complementary alphabet profiles, and their size and minimum-distance requirements are forced solely by the MDS property and repair correctness. This gives a unified route from classical coding-theoretic upper bounds to repair-bandwidth lower bounds. As a consequence, we obtain several explicit lower bounds via Singleton, Hamming, Plotkin, and Griesmer arguments, including known bounds as corollaries. We further formulate a Delsarte-type support-enumerator LP for mixed-alphabet codes and give an exact type-compressed implementation. For fixed sub-packetization \(\ell\), this yields a polynomial-time procedure for evaluating the resulting finite-parameter lower bound.
1 Introduction
The section frames fixed-sub-packetization repair bandwidth as a practical and theoretical problem, then introduces auxiliary mixed-alphabet codes as a route to lower bounds.
1 Introduction
- Large sub-packetization increases the fragments indexed, accessed, and combined during repair, motivating lower bounds for fixed sub-packetization.The broader tradeoff is between repair bandwidth and sub-packetization.Source: §1 · p. 1
- A local repair instance fixes h failed nodes and d helpers and minimizes centralized linear repair bandwidth over codes and choices of those sets.This local objective is weaker than requiring one code to support low-bandwidth repair across a family of instances, but is a basic building block.Source: §1 · p. 2
1.1 Our contributions
- Every linear repair scheme induces null-space and, when d ≥ r, row-space mixed-alphabet codes whose feasibility constrains repair profiles.The null-space code is available for all repair degrees.Source: §1.1 · p. 2
- Singleton-type constraints recover the centralized cut-set bound, while Hamming- and Plotkin-type constraints add profile inequalities and known bounds arise as special cases or relaxations.Griesmer’s bound on the flattened row-space code also gives an explicit lower bound when d ≥ r.Source: §1.1 · p. 3
- For fixed sub-packetization ℓ, type compression reduces the LP to at most (d + 1)ℓ support-type variables and constraints, enabling polynomial-time evaluation in the repair degree.The ordered support-enumerator LP has size 2^d.Source: §1.1 · p. 3
1.2 Technical overview
- Helper kernels record directions invisible to the repair matrix, while helper row spaces record downloaded combinations; MDS conditions constrain both codes’ distances.For the row-space code, the stated MDS-based injectivity and distance conditions apply when d ≥ r.Source: §1.2 · p. 3
2 Preliminaries
The preliminaries define the MDS repair setting and local bandwidth objective, then reduce lower-bound analysis to instances where every surviving node helps.
2 Preliminaries
- An MDS array code stores length-ℓ vectors, and any k nodes determine the data; equivalently, any r parity-check blocks form an invertible matrix.The codeword vectors satisfy the parity-check equations.Source: §2 · p. 4
- A repair matrix recovers h failed nodes when its failed-node block is invertible, and each participating helper transmits rank(MH_j) independent symbols.The repair bandwidth is the sum of the helper download ranks.Source: §2 · p. 4
- The local minimum bandwidth β is minimized over MDS codes, failure sets, helper sets, and valid repair matrices, so its lower bounds apply to every instance with the prescribed parameters.The repair degree counts active helper nodes.Source: §2 · pp. 4–5
- For lower bounds, it suffices to consider the reduced MDS instance with all surviving nodes helping, where the achieved bandwidth is preserved.The projection argument constructs reduced parity-check blocks by applying a matrix that annihilates the non-helper blocks.Source: §2 · p. 5
3 Reduction to Mixed-Alphabet Codes
The section reduces centralized linear repair schemes to auxiliary mixed-alphabet codes built from helper kernels and row spaces. Their required sizes and distances impose necessary conditions on feasible repair profiles.
3 Reduction to Mixed-Alphabet Codes
- The helper-wise kernel and row-space dimensions form complementary profiles, with a_j + b_j = ℓ and α = dℓ − β.The kernel spaces record directions not accessed by the repair matrix, while the row spaces record downloaded combinations.Source: §3 · p. 6
3.1 The null-space auxiliary code
- The null-space code A uses helper-kernel alphabets, has block distance at least r + 1, and is trivial when d ≤ r.Its construction applies for every repair degree.Source: §3.1 · pp. 6–7
3.2 The row-space auxiliary code
- When d ≥ r, the row-space code B has size q^(hℓ) and block distance at least d − r + 1.B is a linear mixed-alphabet code whose coordinate alphabets are the helper row spaces.Source: §3.2 · p. 7
4 Combinatorial Profile Bounds
Classical coding bounds become necessary constraints on repair-bandwidth profiles through the auxiliary codes. These constraints recover the centralized cut-set bound and yield explicit bandwidth lower bounds, with additional consequences handled numerically.
4.1 Basic Profile Constraints
- Singleton-type puncturing gives Σ_{j∈J} a_j ≤ (r − h)ℓ for every r-subset J, and summing its equivalent form yields β ≥ dhℓ.The summed inequality is the centralized cut-set bound.Source: §4.1 · p. 8
- Hamming-type constraints use disjoint mixed-alphabet Hamming balls, while Plotkin-type constraints apply when d ≥ r and the distance is large relative to helper coordinates.The Hamming argument uses the auxiliary codes’ minimum-distance and size requirements.Source: §4.1 · pp. 8–9
- The profile constraints recover the projective-counting bound of [LW26] and, for h = 1 and d = n − 1, Plotkin relaxations recover bounds of [GW16] and [Wu26].Source: §4.1 · pp. 9–10
4.2 Representative Lower Bounds on Repair Bandwidth
- Representative explicit bounds include a Griesmer bound from flattening B and a Hamming-type bound with e = ⌊r/2⌋; the Plotkin-Jensen bound applies when d ≥ r.Flattening B gives a scalar code of length β, dimension hℓ, and minimum distance at least d − r + 1.Source: §4.2 · pp. 10–11
- Some combinatorial consequences do not yield uniformly clean lower bounds and are left for numerical handling; the LP is presented for tighter finite-parameter bounds.Source: §4.2 · p. 11
5 Linear-Programming Bounds
The section adapts Delsarte’s support-enumerator LP to mixed-alphabet codes, compresses it exactly by coordinate type, and uses it to bound feasible repair bandwidth profiles. For fixed sub-packetization, the resulting procedure is polynomial-time, and the numerical examples show that it can improve on closed-form bounds while leaving a gap to construction benchmarks.
5 Linear-Programming Bounds
- The bandwidth profile has no zero-dimensional coordinates, while its complementary null-space profile may include them.The LP setup uses helper-coordinate dimensions b_j from 1 to ℓ and complementary dimensions a_j from 0 to ℓ−1.Source: §5 · p. 12
5.1 A mixed-alphabet LP method
- Theorem 13 upper-bounds the size of a mixed-alphabet linear code with a prescribed coordinate-dimension profile and minimum block distance using a support-enumerator LP.Its constraints encode the zero word, minimum distance, non-negativity, and a dual non-negativity condition.Source: §5 · p. 11, §5.1 · p. 13
5.2 Exact type compression
- Exact type compression preserves the LP optimum by grouping supports across coordinates with equal local dimension.The ordered LP has one variable per support subset; averaging over equal-dimension coordinate permutations and lifting back preserves feasibility and objective value.Source: §5.2 · pp. 13, 15
5.3 LP lower bound for repair bandwidth
- Theorem 16 converts LP-admissible bandwidth profiles into a lower bound on repair bandwidth, and an empty admissible set rules out a feasible scheme in the reduced full-helper instance.Every feasible scheme induces an admissible profile; the bound minimizes bandwidth over those profiles.Source: §5.3 · p. 16
- When d ≥ r, the repair-bandwidth profile must also satisfy the row-space code’s LP size constraint.The row-space code has type profile m and size q^(hℓ); when d < r, this row-space condition does not apply.Source: §5.3 · pp. 15–16
- For fixed sub-packetization ℓ, Algorithm 1 evaluates the LP lower bound in polynomial time in the repair degree.The type-compressed LP has size polynomial in the repair degree for fixed ℓ, unlike the uncompressed LP’s 2^d subset scale.Source: §5.3 · p. 17
5.4 Numerical examples
- For h = 1, r = 3, ℓ = 2, q = 5, the LP bound improves on the closed-form bound but remains below the traditional MDS repair baseline.Figure 1 compares the cut-set, closed-form, type-compressed LP, and traditional MDS repair bandwidths as d varies.Source: §5.4 · p. 17, Figure 1 · p. 18
- The numerical examples show that the LP bound can improve on explicit closed-form bounds, while a gap remains to the construction benchmarks.Figure 2 compares lower bounds and, separately, the LP bound against Reed–Solomon and LESS repair bandwidths.Source: §5.4 · pp. 18–19, Figure 2 · p. 18
6 Conclusion
The paper derives local lower bounds for centralized linear repair by reducing repair schemes to auxiliary mixed-alphabet codes and applying classical coding bounds. It also gives an exact type-compressed LP procedure that is polynomial-time for fixed sub-packetization, while identifying local-to-global compatibility as an open direction.
6 Conclusion
- Any centralized linear repair scheme induces null-space and, when d ≥ r, row-space mixed-alphabet codes that yield finite-parameter constraints on feasible bandwidth profiles.Singleton-, Hamming-, Plotkin-, and Griesmer-type bounds are applied to these auxiliary codes.Source: §6 · p. 19
- For fixed sub-packetization ℓ, exact type compression reduces the support-enumerator LP to polynomial size in d and gives a polynomial-time procedure for evaluating the bound.The compression groups supports by type without changing the LP optimum.Source: §6 · p. 19
- A future question is when local repair optima for fixed failure and helper sets can be made compatible with one code’s global repair objective.Global optimality requires a single code to support low-bandwidth repair across a prescribed family of repair patterns.Source: §6 · p. 19