We study the exact and optimal repair of multiple failures in codes for distributed storage. More particularly, we examine the use of interference alignment to build exact scalar minimum storage coordinated regenerating codes (MSCR). We show that it is possible to build codes for the case of k = 2 and d > k by aligning interferences independently but that this technique cannot be applied as soon as k > 2 and d > k. Our results also apply to adaptive regenerating codes.
For the case of multiple failures @math , only scalar MSCR codes ( @math ) have been considered. Previous work @cite_19 only considered the degenerated case of @math where the costs of coordinated cooperative regenerating codes is equivalent to the costs of erasure correcting codes with lazy repairs. In this work, where @math , the repair boils down to repairing in parallel @math independent erasure correcting codes (, no network coding is needed). The work we present in this paper is the first to consider a non-degenerated case @math and to apply interference alignment when multiple failures are repaired simultaneously leading to the codes we define in , which are restricted to @math . Furthermore, in , we show that independant interference alignment with scalar codes is not sufficient for building exact MSCR codes when @math . With respect to the MBR point, the best known construction @cite_11 are scalar codes based on the product matrix framework and allow the repair for any value of @math . Some interesting alternative codes @cite_1 @cite_15 allow repair by transfer (, without performing any linear operation) and rely on fractional repetition codes.
@cite_19 @cite_15 @cite_1 @cite_11
2063987864 2492240243 2105695025 2963754880
We give an explicit construction of exact cooperative regenerating codes at the MBCR (minimum bandwidth cooperative regeneration) point. Before the paper, the only known explicit MBCR codes are given with parameters n = d + r and d = k, while our construction applies to all possible values of n, k, d, r. The code has a brief expression in the polynomial form and the data reconstruction is accomplished by bivariate polynomial interpolation. It is a scalar code and operates over a finite field of size q ≥ n. Besides, we establish several subspace properties for linear exact MBCR codes. Based on these properties we prove that linear exact MBCR codes cannot achieve repair-by-transfer. 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. Several works have developed vector-linear maximum-distance separable (MDS) storage codes that minimize the total communication cost required to repair a single coded symbol after an erasure, referred to as repair bandwidth (BW). Vector codes allow communicating fewer sub-symbols per node, instead of the entire content. This allows non trivial savings in repair BW. In sharp contrast, classic codes, like Reed-Solomon (RS), used in current storage systems, are deemed to suffer from naive repair, i.e. downloading the entire stored message to repair one failed node. This mainly happens because they are scalar-linear. In this work, we present a simple framework that treats scalar codes as vector-linear. In some cases, this allows significant savings in repair BW. We show that vectorized scalar codes exhibit properties that simplify the design of repair schemes. Our framework can be seen as a finite field analogue of real interference alignment. Using our simplified framework, we design a scheme that we call clique-repair which provably identifies the best linear repair strategy for any scalar 2-parity MDS code, under some conditions on the sub-field chosen for vectorization. We specify optimal repair schemes for specific (5,3)- and (6,4)-Reed-Solomon (RS) codes. Further, we present a repair strategy for the RS code currently deployed in the Facebook Analytics Hadoop cluster that leads to 20 of repair BW savings over naive repair which is the repair scheme currently used for this 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.