In a distributed storage system, recovering from multiple failures is a critical and frequent task that is crucial for maintaining the system's reliability and fault-tolerance. In this work, we focus on the problem of repairing multiple failures in a centralized way, which can be desirable in many data storage configurations, and we show that a significant repair traffic reduction is possible. First, the fundamental tradeoff between the repair bandwidth and the storage size for functional repair is established. Using a graph-theoretic formulation, the optimal tradeoff is identified as the solution to an integer optimization problem, for which a closed-form expression is derived. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR) and minimum bandwidth multi-node repair (MBMR) points, are obtained. Second, we describe a general framework for converting single erasure minimum storage regenerating codes to MSMR codes. The repair strategy for @math failures is similar to that for single failure, however certain extra requirements need to be satisfied by the repairing functions for single failure. For illustration, the framework is applied to product-matrix codes and interference alignment codes. Furthermore, we prove that the functional MBMR point is not achievable for linear exact repair codes. We also show that exact-repair minimum bandwidth cooperative repair (MBCR) codes achieve an interior point, that lies near the MBMR point, when @math , @math being the minimum number of nodes needed to reconstruct the entire data. Finally, for @math and @math , where @math is the number of helper nodes during repair, we show that the functional repair tradeoff is not achievable under exact repair, except for maybe a small portion near the MSMR point, which parallels the results for single erasure repair by
The number of nodes involved in the repair of a single node, known as locality, is another important measure of node repair efficiency @cite_41 . Various bounds and code constructions have been proposed in the literature @cite_41 @cite_19 . Recent works have investigated the problem of multiple node repair under locality constraints @cite_21 @cite_6 .
@cite_41 @cite_19 @cite_21 @cite_6
2507181206 2949307695 2102047288 2080339104
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. Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. We show that cooperative model is stronger than the centralized one, in the sense that MDS codes with optimal repair bandwidth under the former model have the same property under the latter one. In this paper we present explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any @math such that @math we construct explicit @math MDS codes over the field @math of size @math that can optimally repair any @math erasures from any @math helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the other failed nodes. This shows that two rounds of communication in cooperative repair always suffice, and that the proposed codes achieve the optimal repair bandwidth using the smallest possible number of rounds. We consider exact repair of failed nodes in maximum distance separable (MDS) code based distributed storage systems. It is well known that an (n, k) MDS code can tolerate failure (erasure) of up to n − k storage disks, when the code is used to store k information elements over n distributed storage disks. The focus of this paper is optimal recovery, in terms of repair bandwidth - the amount of data to be downloaded to repair a failed node - for a single failed node. When a single node fails, it has been previously shown by Dimakis et. al. that the amount of repair bandwidth is at least equation units, when each storage disk stores ℒ units of data. The achievability of this lower bound of equation units, for arbitrary values of (n, k); has been shown previously using asymptotic code constructions based on asymptotic interference alignment. However, the existence of finite codes satisfying this lower bound has been shown only for specific regimes of (n, k) and their existence for arbitrary values of (n, k) remained open. In this paper, we provide the first known construction of a finite code for arbitrary (n, k), which can repair a single failed systematic node by downloading exactly equation units of data. The code that we construct is based on permutation matrices and hence termed the Permutation Code. Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.