In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node. Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code. This survey provides an overview of the efforts in this direction that have taken place over the past decade.
In @cite_182 , the authors improve the Guruswami-Wootters approach to a larger class of parameters. In @cite_87 , the authors provide a family of RS codes that has asymptotically optimal repair bandwidth with respect to the cut-set bound. This result is further developed in @cite_184 to reduce the sub-packetization levels. In @cite_112 , the authors present RS codes that meet the MSR point for all parameters: @math . Bandwidth-efficient recovery from multiple erasures in RS codes is addressed in @cite_153 and is further extended to include general scalar MDS codes in @cite_145 . In @cite_152 , the authors present codes that universally achieve the optimal bandwidth points for all parameters @math and @math simultaneously.
@cite_87 @cite_152 @cite_184 @cite_145 @cite_112 @cite_153 @cite_182
2507181206 2765604633 2963000079 2733645754 2962858508 2950353718 2577154367
Given any r and n, we present an explicit construction of high-rate maximum distance separable (MDS) array codes that can optimally repair any d failed nodes from any h helper nodes for all h, 1 ≤ h ≤ r and d, k ≤ d ≤ n − h simultaneously. These codes can be constructed over any base field F as long as |F| ≥ sn; where s = lcm(1, 2, …, r). The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Our results present a significant improvement over earlier results which can only construct explicit codes for the case of at most 3 parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In the second part of the paper we give an explicit construction of Reed-Solomon codes with asymptotically optimal repair bandwidth. The repair bandwidth of a code is the minimum amount of data required to repair one or several failed nodes (erasures). For MDS codes, the repair bandwidth is bounded below by the so-called cut-set bound, and codes that meet this bound with equality are said to support optimal repair of one or multiple failed nodes. We consider the problem of repairing multiple failed nodes of Reed-Solomon (RS) codes. In a recent work with I. Tamo (Proc. IEEE FOCS 2017), we gave the first explicit construction of RS codes with optimal repair of any single failed node from any subset of helper nodes. In this paper, we construct explicit RS codes that universally achieve the cut-set bound for the repair of any number of failed nodes from any set of helper nodes. Moreover, the node size of our codes is close to the optimal (smallest possible) node size of codes with such property. An (n, k, l) MDS code of length n, dimension k and sub-packetization l over a finite field F is a set of n symbol vectors of length l over F with the property that any k vector can recover the entire data of kl symbols. When a node fails we can recover it by downloading symbols from the surviving nodes, and the total number of symbols downloaded in th worst case is the repair bandwidth of the code. By the cut-se bound, the repair bandwidth of an (n, k, l) MDS code is at leas (n − 1)l (n − k). There are several constructions of (n, k, l) MDS codes whose repair bandwidths meet or asymptotically meet the cut-se bound. Letting r = n − k denote the number of parities Ye and Barg constructed (n, k, rn) Reed-Solomon codes the asymptotically meet the cut-set bound. Ye and Barg also constructed optimal bandwidth and optimal update (n, k, rn MDS codes. A key idea in these constructions is to expand integers in base r. We show in this paper that, when r is an integral power, w can significantly reduce the sub-packetization of the Ye-Barg constructions while achieving asymptotically optimal repair bandwidth. As an example, when r = 2m, we achieve the sub-packetization of 2m+n−1, which improves upon the sub packetization of 2mn in the Ye-Barg constructions. In general when r = sm for an integer s  2, our codes have sub packetization l = sm+n−1 = rsn−1. Specifically, in the casi r = sm, we obtain an (n, k, sm+n=1) Reed-Solomon code an an optimal update (n, k, sm+n−1) MDS code, which both have asymptotically optimal repair bandwidth. In order to obtain these results, we extend and generalize the r-ary expansion idea in the Ye-Barg constructions. Even when r is not an integral power, we can still obtain (n, k, sm+n−1) Reed-Solomon codes and optimal update (n, k, sm+n−1) MDS codes by choosing positive integers s an m such that sm  r. In this case, however, the resulting codes have bandwidth that is near-optimal rather than asymptotically optimal. In distributed storage, erasure codes -- like Reed-Solomon Codes -- are often employed to provide reliability. In this setting, it is desirable to be able to repair one or more failed nodes while minimizing the repair bandwidth. In this work, motivated by Reed-Solomon codes, we study the problem of repairing multiple failed nodes in a scalar MDS code. We extend the framework of (Guruswami and Wootters, 2017) to give a framework for constructing repair schemes for multiple failures in general scalar MDS codes, in the centralized repair model. We then specialize our framework to Reed-Solomon codes, and extend and improve upon recent results of (, 2017). The repair problem for an (n, k) error-correcting code calls for recovery of an unavailable coordinate of the codeword by downloading as little information as possible from a subset of the remaining coordinates. Using the terminology motivated by coding in distributed storage, we attempt to repair a failed node by accessing information stored on d helper nodes, where k &#x227C; d &#x227C; n &#x2013; 1, and using as little repair bandwidth as possible to recover the lost information.By the so-called cut-set bound (, 2010), the repair bandwidth of an (n,k = n &#x2013; r) MDS code using d helper nodes is at least dl (d + 1 &#x2013; k), where l is the size of the node. A number of constructions of MDS array codes have been shown to meet this bound with equality. In a related but separate line of work, Guruswami and Wootters (2016) studied repair of Reed-Solomon (RS) codes, showing that it is possible to perform repair using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality, which has been an open problem in coding theory.In this work we present a solution to this problem, constructing RS codes of length n over the field of size (ql, l = exp((1 + o(1)n log n) that meet the cut-set bound. We also prove an almost matching lower bound on l, showing that super-exponential scaling is both necessary and sufficient for achieving the cut-set bound using linear repair schemes. More precisely, we prove that for scalar MDS codes (including the RS codes) to meet this bound, the sub-packetization l must satisfy l &#x227D; exp((1 + o(1))k log k). Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. As all traces belong to a subfield of the defining field of the RS code and many of them are linearly dependent, the total repair bandwidth is significantly reduced compared to that of the naive repair scheme. We extend the trace collection technique to cope with multiple erasures. Reed-Solomon codes have found many applications in practical storage systems, but were until recently considered unsuitable for distributed storage applications due to the widely-held belief that they have poor repair bandwidth. The work of Guruswami and Wootters (STOC'16) has shown that one can actually perform bandwidth-efficient linear repair with Reed-Solomon codes: When the codes are over the field F q t and the number of parities r ≥ qs, where (t − s) divides t, there exists a linear scheme that achieves a repair bandwidth of (n − 1)(t − s) logg q bits. We extend this result by showing the existence of such a linear repair scheme for every 1 ≤ s t and r = qs. Additionally, we improve the lower bound on the repair bandwidth for Reed-Solomon codes, also established in the work of Guruswami and Wootters.