An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes

An (n, k, l)-vector MDS code over a field F is a F-linear subspace of (F-l)(n) of dimension kl, such that any k (vector) symbols of the codeword suffice to determine the remaining r = n - k (vector) symbols. The length l 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 l/r field elements (which is known to be the minimum 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 l greater than or similar to r(k/r). Our main result is an almost tight lower bound showing that for an MSR code, one must have l >= exp(Omega(k/r)). Previously, a lower bound of approximate to exp(root k/r), and a tight lower bound for a restricted class of "optimal access" MSR codes, were known.