Optimal limits found for repairing data with fixed code splitting
From Linear Exact Repair to Mixed-Alphabet Codes: The Bandwidth-Subpacketization Tradeoff of MDS Array Codes
Information Theory
Summary
Distributed storage systems save data efficiently using special error-correcting codes, but fixing broken parts requires bandwidth that depends on how the data is split. The authors study how much bandwidth is needed when data splits are fixed and code repair is done linearly. They link repair limits to two types of mixed-alphabet codes, which are constrained by the system's properties. This connection lets them use known coding theory bounds to prove new lower bounds on repair bandwidth, and gives a way to compute these limits efficiently for any fixed data split.
What this means in practice
- •For cloud storage engineers: Determine minimal bandwidth needed to repair data failures given fixed data chunk sizes in distributed storage systems.
- •For network protocol designers: Use bandwidth lower bounds to optimize repair communication protocols for fault tolerance with fixed code parameters.
A theory result. No direct application yet.
Authors
Zihao Zhang, Guodong Li, Sihuang Hu
Abstract
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.