A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> The total porosity of a subterranean formation is calculated by summing the effective Porosity and the clay bound water (CBW) porosity. With the invention described in this patent, the distortion effects of clay bound water (CBW) porosity on the measurement of total porosity is filtered out. The effects will be more significant in slialy sand where the CBW porosity component of total porosity is abundant. The correct NMR transverse relaxation time (T2) spectra distribution is essential to a determination of capillary bound fluid (BVI) partial porosity and the Spectral Bulk Volume Irreducible (SBVI) model. The same data correction concept can be applied to make a meaningful comparison of well logs or laboratory core NMR data that are obtained with different interecho time (TE) sampling periods. <s> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> Peer-to-peer systems are positioned to take advantage of gains in network bandwidth, storage capacity, and computational resources to provide long-term durable storage infrastructures. In this paper, we quantitatively compare building a distributed storage infrastructure that is self-repairing and resilient to faults using either a replicated system or an erasure-resilient system. We show that systems employing erasure codes have mean time to failures many orders of magnitude higher than replicated systems with similar storage and bandwidth requirements. More importantly, erasure-resilient systems use an order of magnitude less bandwidth and storage to provide similar system durability as replicated systems. <s> BIB002 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> This paper exhibits a class of universal Raptor codes: for a given integer k, and any real /spl epsiv/>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + /spl epsiv/) is sufficient to recover the original k symbols, with high probability. Each output symbol is generated using O(log(1//spl epsiv/)) operations, and the original symbols are recovered from the collected ones with O(klog(1//spl epsiv/)) operations. <s> BIB003 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> We consider the problem of recovering from a single node failure in a storage system based on an (n, k) MDS code. In such a scenario, a straightforward solution is to perform a complete decoding, even though the data to be recovered only amount to 1/kth of the entire data. This paper presents techniques that can reduce the network traffic incurred. The techniques perform algebraic alignment so that the effective dimension of unwanted information is reduced. <s> BIB004 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. On one end of this spectrum of Regenerating Codes are Minimum Storage Regenerating (MSR) codes that can match the minimum storage cost of MDS codes while also significantly reducing repair bandwidth. In this paper, we describe Exact-MSR codes which allow for any failed nodes (whether they are systematic or parity nodes ) to be regenerated exactly rather than only functionally or information-equivalently. We show that Exact-MSR codes come with no loss of optimalitywith respect to random-network-coding based MSR codes (matching the cutset-based lower bound on repair bandwidth) for the cases of: (a) k/n � 1/2; and (b) k � 3. Our constructive approach is based on interference alignment techniques, and, unlike the previous class of random-network-coding based approaches, we provide explicit and deterministic coding schemes that require a finite-field size of at most 2(n − k). <s> BIB005 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> Regenerating codes allow distributed storage systems to recover from the loss of a storage node while transmitting the minimum possible amount of data across the network. We search for examples of Minimum Storage Regenerating Codes. To exhaustively search the space of potential codes, we reduce the potential search space in several ways. We impose an additional symmetry condition on codes that we consider. We specify codes in a simple alternative way, using additional recovered coefficients rather than transmission coefficients. We place codes into equivalence classes to avoid redundant checking. We find MSR codes for the parameters n = 5 and k = 3 in various fields. We demonstrate that it is possible for such codes to be composed of vectors in general position. <s> BIB006 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> We consider the problem of minimizing the bandwidth required to repair a failed node when data is stored across n nodes in a distributed manner, so as to facilitate reconstruction of the entire data by connecting to any k out of the n nodes. We provide explicit and optimal constructions which permit exact replication of a failed systematic node. <s> BIB007 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n=d+1 . In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d ≥ 2k-2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n=d+1, k, d ≥ 2k-1]. <s> BIB008 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> We consider a set up where a file of size M is stored in n distributed storage nodes, using an (n,k) minimum storage regenerating (MSR) code, i.e., a maximum distance separable (MDS) code that also allows efficient exact-repair of any failed node. The problem of interest in this paper is to minimize the repair bandwidth B for exact regeneration of a single failed node, i.e., the minimum data to be downloaded by a new node to replace the failed node by its exact replica. Previous work has shown that a bandwidth of B=[M(n-1)]/[k(n-k)] is necessary and sufficient for functional (not exact) regeneration. It has also been shown that if k 1/2 remains open for k>3 and it has been shown that there is an extra bandwidth cost for exact repair over functional repair in this case. In this work, we adopt into the distributed storage context an asymptotically optimal interference alignment scheme previously proposed by Cadambe and Jafar for large wireless interference networks. With this scheme we solve the problem of repair bandwidth minimization for (n,k) exact-MSR codes for all (n,k) values including the previously open case of k > \max(n/2,3). Our main result is that, for any (n,k), and sufficiently large file sizes, there is no extra cost of exact regeneration over functional regeneration in terms of the repair bandwidth per bit of regenerated data. More precisely, we show that in the limit as M approaches infinity, the ratio B/M = (n-1)/(k(n-k))$. <s> BIB009 </s> A Survey on Network Codes for Distributed Storage <s> III. MODEL II: EXACT REPAIR <s> We show that the maximization of the sum degrees-of-freedom for the static flat-fading multiple-input multiple-output (MIMO) interference channel (IC) is equivalent to a rank constrained rank minimization problem (RCRM), when the signal subspaces span all available dimensions. The rank minimization corresponds to maximizing interference alignment (IA) so that interference spans the lowest dimensional subspace possible. The rank constraints account for the useful signal subspaces spanning all available spatial dimensions. That way, we reformulate the IA requirements to requirements involving ranks. Then, we present a convex relaxation of the RCRM problem inspired by recent results in compressed sensing and low-rank matrix completion theory that rely on approximating rank with the nuclear norm. We show that the convex envelope of the sum of ranks of the interference matrices is the normalized sum of their corresponding nuclear norms and replace the rank constraints with asymptotically equivalent and tractable ones. We then tune our heuristic relaxation for the multicell interference channel. We experimentally show that in many cases the proposed algorithm attains perfect interference alignment and in some cases outperforms previous approaches for finding precoding and receive matrices for interference alignment. <s> BIB010
As we discussed, the repair-storage tradeoff for functional repair can be completely characterized by analyzing the cutset of the information flow graphs. However, as mentioned earlier, functional repair is of limited practical interest since there is a need to maintain the code in systematic form. Also, under functional repair, significant system overhead is incurred in order to continually update repairing-and-decoding rules whenever a failure occurs. Moreover, the random-network-coding-based solution for the function repair can require a huge finite-field size to support a dynamically expanding graph size (due to continual repair). This can significantly increase the computational complexity of encoding and decoding. Furthermore, functional repair is undesirable in storage security applications in the face of eavesdroppers. In this case, information leakage occurs continually due to the dynamics of repairing-and-decoding rules that can be potentially observed by eavesdroppers  . These drawbacks motivate the need for exact repair of failed nodes. This leads to the following question: Is it possible to achieve the cutset lower bound region presented, with the extra constraint of exact repair? Recently, significant progress has been made on the two extreme points of the family of regenerating codes (and arguably most interesting): the MBR point BIB001 and the MSR point BIB004 , BIB007 , BIB005 . Rashmi et al. BIB001 showed that for d ¼ n À 1, the optimal MBR point can be achieved with a deterministic scheme requiring a small finite-field size and repair bandwidth matching the cutset bound of BIB003 . For the MSR point, Wu and Dimakis BIB004 showed that it can be attained for the cases of k ¼ 2 and k ¼ n À 1 when d ¼ n À 1. Subsequently, Shah et al. BIB007 established that, for ðk=nÞ > ð1=2Þ þ ð2=nÞ, cutset bounds cannot be achieved for exact repair under scalar linear codes (i.e., ¼ 1) where symbols are not allowed to be split into arbitrarily small subsymbols as with vector linear codes.  For large n, this case boils down to ðk=nÞ > ð1=2Þ. Suh and Ramchandran BIB005 showed that exact-MSR codes can match the cutset bound of (5) for the case of ðk=nÞ ð1=2Þ and d ! 2k À 1. BIB002 For the in-between regime ðk=nÞ 2 ð1=2; ð1=2Þ þ ð2=nÞ, Cullina et al. BIB006 and Suh and Ramchandran BIB005 showed that cutset bounds are achievable for the case of k ¼ 3. A construction that can match the cutset bound for the MBR point for all n; k; d and for MSR codes if the rate ðk=nÞ ð1=2Þ was presented by Rashmi et al. BIB008 . Finally, it was very recently established that MSR codes that can match the repair communication cutset bound for all n; k exist asymptotically. This surprising result was independently obtained in BIB005 and BIB009 by using the breakthrough technique of symbol extension introduced by Cadambe and Jafar  . It is surprising how symbol extension, a technique developed to exploit independent fading of wireless channels, maps exactly to problem of exact repair at the MSR point. Recent work of Papailiopoulos et al. BIB010 ,  explores this connection further. We note that while this work shows that high-rate exact MSR codes exist, the constructions of BIB005 and BIB009 are not practical since they require exponential field size and subpacketization. Concerning the intermediate points beyond MSR and MBR, finding the fundamental limits of storage and repair communication remains a challenging open problem. We now briefly summarize some of these recent results.