A Survey on Network Codes for Distributed Storage <s> A. Various Repair Models <s> We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems. <s> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> A. Various Repair Models <s> We consider the problem of information flow in networks. In particular, we relate the question whether a set of desired connections can be accommodated in a network to the problem of finding a point on a variety defined over a suitable field. This approach lends itself to the derivation of a number of theorems concerning the feasibility of a communication scenario involving failures. <s> BIB002 </s> A Survey on Network Codes for Distributed Storage <s> A. Various Repair Models <s> Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node. <s> BIB003 </s> A Survey on Network Codes for Distributed Storage <s> A. Various Repair Models <s> We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching 1 with the code length. We also demonstrate that random linear coding performs compression when necessary in a network, generalizing error exponents for linear Slepian-Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks <s> BIB004 </s> A Survey on Network Codes for Distributed Storage <s> A. Various Repair Models <s> Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network. In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called regenerating codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, regenerating codes can reduce maintenance bandwidth use by 25% or more compared with the best previous design - a hybrid of replication and erasure codes - while simplifying system architecture. <s> BIB005 </s> A Survey on Network Codes for Distributed Storage <s> A. Various Repair Models <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> BIB006
In the repair examples shown in Figs. 2 and 3, the newcomer constructs exactly the two blocks that were in failed node. Note, however, that our definition of repair only requires that the new node forms an ðn; kÞ MDS code property (that any k nodes out of n suffice to recover the original whole data), when combined with existing nodes. In other words, the new node could be forming new linear combinations that were different from the ones in the lost node; a requirement that is strictly easier to satisfy. Three versions of repair have been considered in the literature: exact repair, functional repair, and exact repair of systematic parts. In exact repair, the failed blocks are exactly regenerated, thus restoring exactly the lost encoded blocks with their exact replicas. In functional repair, the requirement is relaxed: the newly generated blocks can contain different data from that of the failed node as long as the repaired system maintains the MDS-code property. The exact repair of the systematic part is a hybrid repair model lying between exact repair and functional repair. In this hybrid model, the storage code is always a systematic in the previous storage system failed. The issue is to repair the failure by creating a new node (the newcomer) that still forms a ð4; 2Þ MDS code. In this example, it is possible to obtain exact repair by communicating three blocks, which is the information-theoretic minimum cutset bound. Fig. 3 . Repairing the last node: in some cases, it is necessary for code (meaning that one copy of the data exists in uncoded form). The systematic part is exactly repaired upon failures and the nonsystematic part follows a functional repair model where the repaired version may be different from the original copy. See Fig. 4 for an illustration. There is one important benefit in keeping the code in systematic form: as shown in Fig. 1 , if the code contains the original data as a subset, reading parts of the data can be performed very quickly by just accessing the corresponding storage node without requiring decoding. Interestingly, as we will see, exact repair, which is the most interesting problem in practice, is also the most challenging one and determining a large part of the achievable region remains open. The functional repair problem is completely understood because, as shown in BIB005 , it can be reduced to a multicasting problem on an appropriately constructed graph called the information flow graph. The pioneering work of Ahlswede et al. BIB001 characterized the multicasting rates by showing that cutset bounds are achievable. Further work showed that linear network coding suffices BIB003 , BIB002 and random linear combinations construct good network codes with high probability BIB004 . See also the survey  and references therein. Since functional repair is reduced to multicasting, we can completely characterize the minimum repair bandwidth by evaluating the min-cut bounds and network coding provides effective and constructive solutions. In Section II, we present the results that characterize the achievable functional repair region and show a tradeoff between storage and repair bandwidth. The exact repair problem is strictly harder than functional repair. In exact repair, the new node accesses some existing storage nodes and exactly reproduces the lost coded blocks. As will be described subsequently, repair codes come with fundamental tradeoffs between storage cost and repair bandwidth. The two important special cases involve operating points corresponding to maximal storage and minimal bandwidth versus minimal storage with maximal bandwidth point. Exact repair for the minimal bandwidth operating point is described in Section II-B) and describes the recent work of BIB006 , which develops optimal exact repair codes for this operating point without any loss of optimality with respect to only functional repair. The special case of the operating point that corresponds to minimal storage, which also corresponds to minimizing the repair bandwidth while keeping the same storage cost of MDS codes, turns out to be more challenging. It turns out that, in this case, the new node needs to recover part of the data that are interfering with other data packets. When an information sink receives a set of linear equations and tries to decode for some variables, we call undesired variables, mixed into these equations, interference. It is the need to carefully handle interference that makes the problem difficult. The constructive techniques perform algebraic alignment so that the effective dimension of unwanted information is reduced, thus reducing the repair traffic. These constructive techniques achieve perfect alignment and characterize the repair bandwidth for low-rate MDS codes ðk=n 1=2Þ. Achieving the cut-set bound for high-rate MDS codes is only known to be achievable by asymptotic nonpractical techniques as we discuss subsequently. The exact repair of systematic parts model is a relaxation of the exact repair model. As in the exact repair model, the core constructive techniques are interference alignment and network coding. In Section IV, we will see that this relaxation addresses some problem space not covered by exact repair.