Back to Search
Start Over
An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes.
- Source :
- IEEE Transactions on Information Theory; Dec2021, Vol. 67 Issue 12, p8086-8093, 8p
- Publication Year :
- 2021
-
Abstract
- 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 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 $\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. [ABSTRACT FROM AUTHOR]
- Subjects :
- STORAGE
MAXIMA & minima
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731596
- Full Text :
- https://doi.org/10.1109/TIT.2021.3112286