An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level, Small Field Size and All-Node Repair

Abstract

This paper presents an explicit construction for an $((n,k,d=n-1),(\alpha ,\beta ))$ regenerating code over a field ${\mathbb{F}}_Q$ operating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate $k/n$ as close to $1$ as desired, sub-packetization given by $r^{\frac{n}{r}}$, for $r=(n-k)$, field size no larger than $n$ and where all code symbols can be repaired with the same minimum data download. The construction modifies a prior construction by Sasidharan et. al. which required far larger field-size. A building block appearing in the construction is a scalar MDS code of block length $n$. The code has a simple layered structure with coupling across layers, that allows both node repair and data recovery to be carried out by making multiple calls to a decoder for the scalar MDS code. While this work was carried out independently, there is considerable overlap with a prior construction by Ye and Barg. It is shown here that essentially the same architecture can be employed to construct MSR codes using vector binary MDS codes as building blocks in place of scalar MDS codes. The advantage here is that computations can now be carried out over a field of smaller size potentially even over the binary field as we demonstrate in an example. Further, we show how the construction can be extended to handle the case of $d<(n-1)$ under a mild restriction on the choice of helper nodes.

References in corpus (5)

• Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions
• Explicit constructions of high-rate MDS array codes with optimal repair bandwidth
• Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization
• Minimum Storage Regenerating Codes For All Parameters
• New MDS codes with small sub-packetization and near-optimal repair bandwidth

Cited by in corpus (19)

• Towards Practical Private Information Retrieval from MDS Array Codes
• MSR Codes with Linear Field Size and Smallest Sub-packetization for Any Number of Helper Nodes
• A Generic Transformation for Optimal Node Repair in MDS Array Codes over ${\mathbf{F}}_2$
• Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization
• Constructing MSR codes with subpacketization $2^{n/3}$ for $k+1$ helper nodes
• Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost
• Optimal Repair Layering for Erasure-Coded Data Centers: From Theory to Practice
• PMDS Array Codes With Small Sub-packetization, Small Repair Bandwidth/Rebuilding Access
• The repair problem for Reed-Solomon codes: Optimal repair of single and multiple erasures, asymptotically optimal node size
• Explicit constructions of MSR codes for clustered distributed storage: The rack-aware storage model
• Erasure Coding for Distributed Storage: An Overview
• Capacity bounds for distributed storage
• On Epsilon-MSCR Codes for Two Erasures
• A New Design of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair
• On Lower Bounds on Sub-Packetization Level of MSR codes and On The Structure of Optimal-Access MSR Codes Achieving The Bound
• Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization
• New constructions of cooperative MSR codes: Reducing node size to $\exp (O(n))$
• Codes with Combined Locality and Regeneration Having Optimal Rate, $d_{\text{min}}$ and Linear Field Size
• Erasure Codes for Distributed Storage: Tight Bounds and Matching Constructions