An @math maximum distance separable (MDS) code has optimal repair access if the minimum number of symbols accessed from @math surviving nodes is achieved, where @math . Existing results show that the sub-packetization @math of an @math high code rate (i.e., @math ) MDS code with optimal repair access is at least @math . In this paper, we propose a class of multi-layer transformed MDS codes such that the sub-packetization is @math , where @math , and the repair access is optimal for any single node. We show that the sub-packetization of the proposed multi-layer transformed MDS codes is strictly less than the existing known lower bound when @math , achieving by restricting the choice of @math specific helper nodes in repairing a failed node. We further propose multi-layer transformed EVENODD codes that have optimal repair access for any single node and lower sub-packetization than the existing binary MDS array codes with optimal repair access for any single node. With our multi-layer transformation, we can design new MDS codes that have the properties of low computational complexity, optimal repair access for any single node, and relatively small sub-packetization, all of which are critical for maintaining the reliability of distributed storage systems.
MSR codes with high code rates (i.e, @math ) are important in practice. Some existing constructions of high-code-rate MSR codes are found in @cite_25 @cite_32 @cite_15 @cite_28 @cite_3 . It is shown in @cite_22 that a tight lower bound of the sub-packetization level of high-code-rate MSR codes with optimal repair access is @math . More generally, for any @math MDS code with optimal repair access for each of @math nodes (where @math ), the minimum sub-packetization level is @math .
@cite_22 @cite_28 @cite_32 @cite_3 @cite_15 @cite_25
2765728635 2963754880 2832241482 2963781977 2606114015 2069026918
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. Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with @math information nodes and @math parity nodes is used to encode data in a distributed storage system. It is known that if @math out of the @math nodes are inaccessible and @math surviving (helper) nodes are used to recover the lost data, then we need to download at least @math fraction of the data stored in each of the helper nodes ( , 2010 and , 2013). If this lower bound is achieved for the repair of any @math erased nodes from any @math helper nodes, we say that the MDS code has the @math -optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any @math and @math , we present two explicit constructions of MDS array codes with the @math -optimal repair property for all @math and @math simultaneously. Codes in the first family can be constructed over any base field @math as long as @math , where @math . The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field @math as long as @math . Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property. We propose a generic transformation that can convert any nonbinary @math maximum distance separable (MDS) code into another @math MDS code over the same field such that: 1) some arbitrarily chosen @math nodes have the optimal repair bandwidth and the optimal rebuilding access; 2) for the remaining @math nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved; and 3) the sub-packetization level is increased only by a factor of @math . Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary @math scalar MDS code can be converted into an @math MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal. 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. Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an @math - @math MSR code @math over @math stores a file @math consisting of @math symbols over @math among @math nodes, each storing @math symbols, in such a way that: 1) the file @math can be recovered by downloading the content of any @math of the @math nodes and 2) the content of any failed node can be reconstructed by accessing any @math of the remaining @math nodes and downloading @math symbols from each of these nodes. In practice, the file @math is typically available in uncoded form on some @math of the @math nodes, known as systematic nodes , and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only . Such codes are called systematic–repair MSR codes . Unfortunately, finite– @math constructions of @math MSR codes are known only for certain special cases: either low rate, namely @math , or high repair connectivity, namely @math . Our main result in this paper is a finite– @math construction of systematic-repair @math MSR codes for all possible values of parameters @math . We also introduce a generalized construction for @math MSR codes to achieve the optimal repair bandwidth for all values of @math simultaneously. Maximum distance separable (MDS) array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct, then the rebuilding ratio is 1 (access all the remaining information). However, the interesting and more practical case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between [1 2] and [3 4]; however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a two-erasure correcting code, the rebuilding ratio is [1 2]. In general, we construct a new family of r-erasure correcting MDS array codes that has optimal rebuilding ratio of [1 (r)] in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the cases r=2 and r=3, they use a finite field of size 3 and 4, respectively) and an optimal update property.