An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes

DOI10.1109/TIT.2014.2309000zbMATH Open1360.94374arXiv1305.3498MaRDI QIDQ2986387FDOQ2986387

Authors: Sreechakra Goparaju, Itzhak Tamo, Robert Calderbank 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Distributed storage systems employ codes to provide resilience to failure of multiple storage disks. Specifically, an $(n,k)$ MDS code stores $k$ symbols in $n$ disks such that the overall system is tolerant to a failure of up to $n-k$ disks. However, access to at least $k$ disks is still required to repair a single erasure. To reduce repair bandwidth, array codes are used where the stored symbols or packets are vectors of length $ell$. MDS array codes have the potential to repair a single erasure using a fraction $1/(n-k)$ of data stored in the remaining disks. We introduce new methods of analysis which capitalize on the translation of the storage system problem into a geometric problem on a set of operators and subspaces. In particular, we ask the following question: for a given $(n,k)$, what is the minimum vector-length or sub-packetization factor $ell$ required to achieve this optimal fraction? For emph{exact recovery} of systematic disks in an MDS code of low redundancy, i.e. $k/n>1/2$, the best known explicit codes cite{WTB12} have a sub-packetization factor $ell$ which is exponential in $k$. It has been conjectured cite{TWB12} that for a fixed number of parity nodes, it is in fact necessary for $ell$ to be exponential in $k$. In this paper, we provide a new log-squared converse bound on $k$ for a given $ell$, and prove that $kle2lo{g}_{2}ellleft(lo{g}_{delta}ell+1ight)$, for an arbitrary number of parity nodes $r=n-k$, where $delta=r/(r-1)$.

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

Recommendations

• An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes
• Improved Upper Bounds on Systematic-Length for Linear Minimum Storage Regenerating Codes
• An exponential lower bound on the sub-packetization of MSR codes
• A Framework of Constructions of Minimal Storage Regenerating Codes With the Optimal Access/Update Property
• On the Sub-Packetization Size and the Repair Bandwidth of Reed-Solomon Codes
• A Systematic Piggybacking Design for Minimum Storage Regenerating Codes
• Explicit Minimum Storage Regenerating Codes
• An Outer Bound on the Storage-Bandwidth Tradeoff of Exact-Repair Cooperative Regenerating Codes
• Bounds on the Size and Asymptotic Rate of Subblock-Constrained Codes
• Outer bounds on the storage-repair bandwidth trade-off of exact-repair regenerating codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Combinatorial codes (94B25)

Cited In (6)

• Codes for Distributed Storage
• Subexponential and Linear Subpacketization Coded Caching via Projective Geometry
• A new piggybacking design for systematic MDS storage codes
• Construction of minimum bandwidth regenerating codes with combinatorial design
• Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction
• An Outer Bound on the Storage-Bandwidth Tradeoff of Exact-Repair Cooperative Regenerating Codes

This page was built for publication: An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes

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