MSR Codes with Linear Field Size and Smallest Sub-packetization for Any Number of Helper Nodes

Abstract

The sub-packetization $\ell$ and the field size $q$ are of paramount importance in the MSR array code constructions. For optimal-access MSR codes, Balaji et al. proved that $\ell \ge s^{\lceil n/s\rceil }$, where $s=d-k+1$. Rawat et al. showed that this lower bound is attainable for all admissible values of $d$ when the field size is exponential in $n$. After that, tremendous efforts have been devoted to reducing the field size. However, till now, reduction to linear field size is only available for $d\in \{k+1,k+2,k+3\}$ and $d=n-1$. In this paper, we construct the first class of explicit optimal-access MSR codes with the smallest sub-packetization $\ell =s^{\lceil n/s\rceil }$ for all $d$ between $k+1$ and $n-1$, resolving an open problem in the survey (Ramkumar et al., Foundations and Trends in Communications and Information Theory: Vol. 19: No. 4). We further propose another class of explicit MSR code constructions (not optimal-access) with even smaller sub-packetization $s^{\lceil n/(s+1)\rceil }$ for all admissible values of $d$, making significant progress on another open problem in the survey. Previously, MSR codes with $\ell =s^{\lceil n/(s+1)\rceil }$ and $q=O(n)$ were only known for $d=k+1$ and $d=n-1$. The key insight that enables a linear field size in our construction is to reduce $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ global constraints of non-vanishing determinants to $O_s(n)$ local ones, which is achieved by carefully designing the parity check matrices.

arXiv commentThis paper is reorganized to make it more readable. The lower bounds in Lemma 6 and Lemma 9 are improved

References in corpus (6)

• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
• Zigzag Codes: MDS Array Codes with Optimal Rebuilding
• A Generic Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems
• An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level, Small Field Size and All-Node Repair
• Constructing MSR codes with subpacketization $2^{n/3}$ for $k+1$ helper nodes
• Multilinear Algebra for Minimum Storage Regenerating Codes

Cited by in corpus (1)

• Constructing $(h,d)$ cooperative MSR codes with sub-packetization $(d-k+h)(d-k+1{)}^{\lceil n/2\rceil }$