An @math vector code @math is a collection of @math codewords where @math elements (from the field @math ) in each of the codewords are referred to as code blocks. Assuming that @math , the code blocks are treated as @math -length vectors over the base field @math . Equivalently, the code is said to have the sub-packetization level @math . This paper addresses the problem of constructing MDS vector codes which enable exact reconstruction of each code block by downloading small amount of information from the remaining code blocks. The repair bandwidth of a code measures the information flow from the remaining code blocks during the reconstruction of a single code block. This problem naturally arises in the context of distributed storage systems as the node repair problem [4]. Assuming that @math , the repair bandwidth of an MDS vector code is lower bounded by @math symbols (over the base field @math ) which is also referred to as the cut-set bound [4]. For all values of @math and @math , the MDS vector codes that attain the cut-set bound with the sub-packetization level @math are known in the literature [23, 35]. This paper presents a construction for MDS vector codes which simultaneously ensures both small repair bandwidth and small sub-packetization level. The obtained codes have the smallest possible sub-packetization level @math for an MDS vector code and the repair bandwidth which is at most twice the cut-set bound. The paper then generalizes this code construction so that the repair bandwidth of the obtained codes approach the cut-set bound at the cost of increased sub-packetization level. The constructions presented in this paper give MDS vector codes which are linear over the base field @math .
The code construction based on Hadamard matrices from @cite_14 requires @math and @math . In @cite_27 , propose the zigzag code construction for @math and every value of @math . This construction enables exact repair of only @math (systematic) code blocks. @cite_7 generalize the zigzag code construction to enable exact repair of all code symbols. The constructions presented in @cite_14 @cite_41 @cite_5 work with the sub-packetization level @math which is exponential in @math . For @math and all values of @math , @cite_18 construct exact-repairable MDS vector codes that have optimal repair bandwidth and work with the sub-packetization level @math . Note that for @math , this construction provides the codes with the sub-packetization level which is polynomial in @math . The construction with @math and the similar sub-packetization levels that enable exact-repair of only @math systematic nodes are also presented in @cite_19 @cite_17 . The construction from @cite_18 is generalized to work for all possible values of @math with the sub-packetization level @math in @cite_29 .
@cite_18 @cite_14 @cite_7 @cite_41 @cite_29 @cite_19 @cite_27 @cite_5 @cite_17
2963781977 2492240243 2953340712 2765728635
An @math maximum distance separable (MDS) array code of length @math , dimension @math , and sub-packetization @math is formed of @math matrices over a finite field @math , with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node (recovery of one erased column) can be performed by accessing a set of @math surviving (helper) nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimal-access MDS codes with @math , the sub-packetization @math satisfies the bound @math . In our previous work (IEEE Trans. Inf. Theory, vol. 63, no. 4, 2017), for any @math and @math , we presented an explicit construction of optimal-access MDS codes with sub-packetization @math . In this paper, we take up the question of reducing the sub-packetization value @math to make it to approach the lower bound. We construct an explicit family of optimal-access codes with @math , which differs from the optimal value by at most a factor of @math . These codes can be constructed over any finite field @math as long as @math , and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), which we call group repair with optimal access . In this variation, we assume that the set of @math nodes is partitioned into @math repair groups of size @math , and require that the amount of accessed data for repair is the smallest possible whenever the @math helper nodes include all the other @math nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field @math of size @math , and also afford low-complexity encoding and decoding procedures. This paper presents an explicit construction for an @math regenerating code over a field @math operating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate @math as close to @math as desired, sub-packetization given by @math , for @math , field size no larger than @math 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 @math . 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 @math under a mild restriction on the choice of helper nodes. We present a high-rate @math -MSR code with a sub-packetization level that is polynomial in the dimension @math of the code. While polynomial sub-packetization level was achieved earlier for vector MDS codes that repair systematic nodes optimally, no such MSR code construction is known. In the low-rate regime (i. e., rates less than one-half), MSR code constructions with a linear sub-packetization level are available. But in the high-rate regime (i. e., rates greater than one-half), the known MSR code constructions required a sub-packetization level that is exponential in @math . In the present paper, we construct an MSR code for @math with a fixed rate @math achieveing a sub-packetization level @math . The code allows help-by-transfer repair, i. e., no computations are needed at the helper nodes during repair of a failed node. The first focus of the present paper, is on lower bounds on the sub-packetization level @math of an MSR code that is capable of carrying out repair in help-by-transfer fashion (also called optimal-access property). We prove here a lower bound on @math which is shown to be tight for the case @math by comparing with recent code constructions in the literature. We also extend our results to an @math MDS code over the vector alphabet. Our objective even here, is on lower bounds on the sub-packetization level @math of an MDS code that can carry out repair of any node in a subset of @math nodes, @math where each node is repaired (linear repair) by help-by-transfer with minimum repair bandwidth. We prove a lower bound on @math for the case of @math . This bound holds for any @math and is shown to be tight, again by comparing with recent code constructions in the literature. Also provided, are bounds for the case @math . We study the form of a vector MDS code having the property that we can repair failed nodes belonging to a fixed set of @math nodes with minimum repair bandwidth and in optimal-access fashion, and which achieve our lower bound on sub-packetization level @math . It turns out interestingly, that such a code must necessarily have a coupled-layer structure, similar to that of the Ye-Barg code.