An exponential lower bound on the sub-packetization of MSR codes

DOI10.1145/3313276.3316387MaRDI QIDQ5212838zbMATH OpenOpenAlexFDO

Authors Omar Alrabiah, Venkatesan Guruswami

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.05112

zbMATH Keywords

cutset bounddistributed storage system (DSS)maximum distance separable (MDS) vector codesminimum storage regenerating (MSR) codesMSR subspace familiesrepair bandwidthsub-packetization

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Linear codes (general theory) (94B05)

Abstract: An $(n,k,ell)$-vector MDS code is a $mathbbF$-linear subspace of $(mathbb{F}^{e}ll{)}^n$ (for some field $mathbbF$) of dimension $kell$, 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 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 $ellgtrsim{r}^{k/r}$. Our main result is an almost tight lower bound showing that for an MSR code, one must have $ellgeexp(Omega(k/r))$. This settles a central open question concerning MSR codes that has received much attention. Previously, a lower bound of $approxexp(sqrtk/r)$, and a tight lower bound for a restricted class of "optimal access" MSR codes, were known.

Recommendations

• MDS code constructions with small sub-packetization and near-optimal repair bandwidth
• Scalar MSCR codes via the product matrix construction
• Explicit constructions of MSR codes for clustered distributed storage: the rack-aware storage model
• On lowest density MDS codes
• Repairing Reed-solomon codes

Cited in

(6)

• An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes
• MDS code constructions with small sub-packetization and near-optimal repair bandwidth
• Scalar MSCR codes via the product matrix construction
• Codes for Distributed Storage
• Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction
• On MSR subspace families of lines

This page was built for publication: An exponential lower bound on the sub-packetization of MSR codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212838)