An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes
Omar Alrabiah, Venkatesan Guruswami · IEEE Transactions on Information Theory · 2021
An$(n,k,\ell)$-vector MDS code over a field$\mathbb {F}$is a$\mathbb {F}$-linear subspace of$(\mathbb {F}^\ell)^{n}$of dimension$k\ell $, such that any$k$(vector) symbols of the codeword suffice to determine the remaining$r=n-k$(vector) symbols. The length$\ell $of each codeword symbol is called thesub-packetizationof the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading$\ell /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$\ell \gtrsim r^{k/r}$. Our main result is an almost tight lower bound showing that for an MSR code, one must have$\ell \geqslant \exp (\Omega (k/r))$. Previously, a lower bound of$\approx \exp (\sqrt {k/r})$, and a tight lower bound for a restricted class of “optimal access” MSR codes, were known.