An @math -vector MDS code is a @math -linear subspace of @math (for some field @math ) of dimension @math , such that any @math (vector) symbols of the codeword suffice to determine the remaining @math (vector) symbols. The length @math of each codeword symbol is called the sub-packetization of the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading @math field elements (which is known to be the least possible) from each of the other symbols. MSR codes are attractive for use in distributed storage systems, and by now a variety of ingenious constructions of MSR codes are available. However, they all suffer from exponentially large sub-packetization @math . Our main result is an almost tight lower bound showing that for an MSR code, one must have @math . Previously, a lower bound of @math , and a tight lower bound for a restricted class of "optimal access" MSR codes, were known. Our work settles a central open question concerning MSR codes that has received much attention. Further our proof is really short, hinging on one key definition that is somewhat inspired by Galois theory.
A slight relaxation MSR codes called @math -MSR codes where the helper nodes are allowed to transmit a factor @math more than the cutset bound, i.e., @math symbols, were put forth in @cite_19 . They showed that one can construct @math -MSR codes with sub-packetization @math , and roughly logarithmic sub-packetization is also necessary.
@cite_19
2789573885
We present a high-rate @math -MSR code with a sub-packetization level that is polynomial in the dimension @math of the code. While polynomial sub-packetization level was achieved earlier for vector MDS codes that repair systematic nodes optimally, no such MSR code construction is known. In the low-rate regime (i. e., rates less than one-half), MSR code constructions with a linear sub-packetization level are available. But in the high-rate regime (i. e., rates greater than one-half), the known MSR code constructions required a sub-packetization level that is exponential in @math . In the present paper, we construct an MSR code for @math with a fixed rate @math achieveing a sub-packetization level @math . The code allows help-by-transfer repair, i. e., no computations are needed at the helper nodes during repair of a failed node.