A Survey on Network Codes for Distributed Storage <s> A. Exact-MBR Codes <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> A. Exact-MBR Codes <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> A. Exact-MBR Codes <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> BIB003 </s> A Survey on Network Codes for Distributed Storage <s> A. Exact-MBR Codes <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> BIB004
Theorem 2 (Exact-MBR Codes BIB001 ): For d ¼ n À 1, the cutset lower bound of (8) can be achieved with a deterministic scheme that requires a finite-field alphabet size of at most ðn À 1Þn=2. Fig. 7 illustrates an idea through the example of ðn; k; d; ; Þ ¼ ð5; 3; 4; 4; 4Þ where the maximum file size of M ¼ 9 (matching the cutset bound) can be stored. Let a be nine-dimensional data file. Each node stores four blocks with the form of a t v i , where v i can be interpreted as a 1-D subspace of data file. We simply write only subspace vector to represent an actually stored block. Notice that the degree d is equal to the number of storage blocks to be repaired, i.e., the number of available equations matches the number of desired variables for exact repair of a single node. Hence, for exact repair, there must be at least one duplicated block between node 1 and node i for all i 6 ¼ 1. This observation motivates the following idea. The idea is to have other nodes i ði 6 ¼ 1Þ store each block of node 1, respectively: nodes 2, 3, 4, and 5 store a t v 1 , a t v 2 , a t v 3 , and a t v 4 in its own place, respectively. Notice that for ensuring repair, it suffices to have only one duplicated block between any two storage nodes. Hence, node 2 can store another new three blocks of a t v 5 , a t v 6 , and a t v 7 in 1 This is equivalent to having large block lengths in the classical setting. Under nonlinear and vector linear codes, tightness of cutset bounds remains open. BIB002 The idea was inspired by the code structure in BIB004 where exact repair is guaranteed for the systematic part only. Indeed, it is shown in BIB003 that the code introduced in BIB004 for exact repair of only the systematic nodes can also be used to repair the nonsystematic (parity) node failures exactly provided repair construction schemes are appropriately designed. Fig. 7 . Repairing node 1 for a ð5; 3Þ-MBR code. Note that the number of desired blocks (that need to be repaired) is equal to the number of available equations (that can be downloaded). Hence, the code should be designed such that undesired blocks (interference) are totally avoided. the remaining other places. In accordance with the above procedure, nodes 3, 4, and 5 then copy each of three blocks in their space, respectively. We repeat this procedure until 10 ð¼ 4 þ 3 þ 2 þ 1Þ blocks are stored in total. One can see that this construction guarantees exact repair of any failed node, since at least one block is duplicated between any two storage nodes and also the duplicated block is distinct. See the example in Fig. 7 . The remaining issue is now to design these ten subspace vectors v i , i ¼ 1; . . . ; 10. The detailed construction comes from the MDS-code property that any three nodes out of five need to recover the whole data file. Observe in Fig. 7 that nine distinct vectors can be downloaded from any three nodes. Hence, any ð10; 9Þ MDS code can construct these v i 's. In this example, using the paritycheck code defined over GFð2Þ, we can design the v i 's as follows: v i ¼ e i , 8i ¼ 1; . . . ; 9 and v 10 ¼ ½1; . . . ; 1 t . It has been shown in BIB001 that this idea can be extended to an arbitrary ðn; kÞ case. This construction can be interpreted as an optimal interference avoidance technique. To see this, observe in the figure that the number of desired blocks for exact repair matches the number of available equations that can be downloaded. Hence, the involvement of any undesired blocks (interference) precludes exact repair. A natural question arises: Can this interference-avoidance technique provide solutions to the other extreme MSR point? It turns out that a new idea is needed to cover this point.