A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> It is known that every solvable multicast network has a scalar linear solution over a sufficiently large finite field alphabet. It is also known that this result does not generalize to arbitrary networks. There are several examples in the literature of solvable networks with no scalar linear solution over any finite field. However, each example has a linear solution for some vector dimension greater than one. It has been conjectured that every solvable network has a linear solution over some finite field alphabet and some vector dimension. We provide a counterexample to this conjecture. We also show that if a network has no linear solution over any finite field, then it has no linear solution over any finite commutative ring with identity. Our counterexample network has no linear solution even in the more general algebraic context of modules, which includes as special cases all finite rings and Abelian groups. Furthermore, we show that the network coding capacity of this network is strictly greater than the maximum linear coding capacity over any finite field (exactly 10% greater), so the network is not even asymptotically linearly solvable. It follows that, even for more general versions of linearity such as convolutional coding, filter-bank coding, or linear time sharing, the network has no linear solution <s> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <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> BIB002 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. This redundant storage is optimal, in the sense that two failed disks cannot be retrieved with less than two redundant disks. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The most commonly used scheme that employes optimal redundant storage (i.e., two extra disks) is based on Reed-Solomon (RS) error-correcting codes. This scheme requires computation over finite fields and results in a more complex implementation. For example, we show that the complexity of implementing EVENODD in a disk array with 15 disks is about 50% of the one required when using the RS scheme. The new scheme is not limited to RAID architectures: it can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording. To this end, we also present a decoding algorithm for one column (track) in error. > <s> BIB003 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> A new family of maximum distance separable (MDS) array codes is presented. The code arrays contain p information columns and r independent parity columns, each column consisting of p-1 bits, where p is a prime. We extend a previously known construction for the case r=2 to three and more parity columns. It is shown that when r=3 such extension is possible for any prime p. For larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain class of primes these conditions are satisfied up to r/spl les/8. One of the advantages of the new codes is that encoding and decoding may be accomplished using simple cyclic shifts and XOR operations on the columns of the code array. We develop efficient decoding procedures for the case of two- and three-column errors. This again extends the previously known results for the case of a single-column error. Another primary advantage of our codes is related to the problem of efficient information updates. We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2/sup m/), following an update in a single information bit. This average number is of importance in many storage applications which require frequent updates of information. We show that the upper bound obtained from our codes is close to the lower bound and, most importantly, does not depend on the size of the code symbols. <s> BIB004 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> Proper data placement schemes based on erasure correcting code are one of the most important components for a highly available data storage system. For such schemes, low decoding complexity for correcting (or recovering) storage node failures is essential for practical systems. In this paper, we describe a new coding scheme, which we call the STAR code, for correcting triple storage node failures (erasures). The STAR code is an extension of the double-erasure-correcting EVENODD code, and a modification of the generalized triple-erasure-correcting EVENODD code. The STAR code is an MDS code, and thus is optimal in terms of node failure recovery capability for a given data redundancy. We provide detailed STAR code's decoding algorithms for correcting various triple node failures. We show that the decoding complexity of the STAR code is much lower than those of the existing comparable codes, thus the STAR code is practically very meaningful for storage systems that need higher reliability <s> BIB005 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <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> BIB006 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <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> V. DISCUSSION AND OPEN PROBLEMS <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> BIB008 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> Distributed storage systems provide large-scale reliable data storage by storing a certain degree of redundancy in a decentralized fashion on a group of storage nodes. To recover from data losses due to the instability of these nodes, whenever a node leaves the system, additional redundancy should be regenerated to compensate such losses. In this context, the general objective is to minimize the volume of actual network traffic caused by such regenerations. A class of codes, called regenerating codes, has been proposed to achieve an optimal trade-off curve between the amount of storage space required for storing redundancy and the network traffic during the regeneration. In this paper, we jointly consider the choices of regenerating codes and network topologies. We propose a new design, referred to as RCTREE, that combines the advantage of regenerating codes with a tree-structured regeneration topology. Our focus is the efficient utilization of network links, in addition to the reduction of the regeneration traffic. With the extensive analysis and quantitative evaluations, we show that RCTREE is able to achieve a both fast and stable regeneration, even with departures of storage nodes during the regeneration. <s> BIB009 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> In distributed storage systems that use coding, the issue of minimizing the communication required to rebuild a storage node after a failure arises. We consider the problem of repairing an erased node in a distributed storage system that uses an EVENODD code. EVENODD codes are maximum distance separable (MDS) array codes that are used to protect against erasures, and only require XOR operations for encoding and decoding. We show that when there are two redundancy nodes, to rebuild one erased systematic node, only 3/4 of the information needs to be transmitted. Interestingly, in many cases, the required disk I/O is also minimized. <s> BIB010 </s> A Survey on Network Codes for Distributed Storage <s> V. DISCUSSION AND OPEN PROBLEMS <s> We investigate the problem of maintaining an encoded distributed storage system when some nodes contain adversarial errors. Using the error-correction capabilities that are built into the existing redundancy of the system, we propose a simple linear hashing scheme to detect errors in the storage nodes. Our main result is that for storing a data object of total size M using an (n, k) MDS code over a finite field Fq, up to t1 = ⌊(n − k)/2⌋ errors can be detected, with probability of failure smaller than 1/M, by communicating only O(n(n−k) logM) bits to a trusted verifier. Our result constructs small projections of the data that preserve the errors with high probability and builds on a pseudorandom generator that fools linear functions. The transmission rate achieved by our scheme is asymptotically equal to the min-cut capacity between the source and any receiver. <s> BIB011
We provided an overview of recent results about the problem of reducing repair traffic in distributed storage systems based on erasure coding. Three versions of the repair problems are considered: exact repair, functional repair, and exact repair of systematic parts. In the exact repair model, the lost content is exactly regenerated; in the functional repair model, only the same MDS-code property is maintained before and after repairing; in the exact repair of systematic parts, the systematic part is exactly reconstructed but the nonsystematic part follows a functional repair model. The functional repair problem is in essence a problem of multicasting from a source to an unbounded number of receivers over an unbounded graph. As we showed there is a tradeoff between storage and repair bandwidth and the two extremal points are achieved by MBR and MSR codes. The repair bandwidth is characterized by the min-cut bounds and therefore the functional repair problem is well understood. Problems that require exact repair correspond to network coding problems having sinks with overlapping subset demands. For such problems, cutset bounds are not tight in general and linear codes might not even suffice BIB001 . The recent work we discussed BIB002 showed that for MBR codes the repair bandwidth given by the cutset bound is achievable for the interesting case of d ¼ n À 1. The minimum-storage point seems harder to understand. The best known constructions BIB006 we presented match the cutset bound for k=n 1=2 for the interesting regime of connectivity d 2 ½2k À 1; n À 1. A corresponding negative result BIB007 established that, for ðk=nÞ > ð1=2Þ þ ð2=nÞ, the cutset bound cannot be achieved by scalar interference-alignment-based linear schemes. However, the symbol extension BIB006 , BIB008 method showed that the cutset bound can be asymptotically approached for very large subpacketization . Table 1 summarizes what is known for the repair bandwidth region and an online editable bibliography (Wiki) can be found online  . All the cases marked correspond to regimes where the cutset bound is known to be achievable. To the best of our knowledge there are no information-theoretic upper bounds other than the cutset bound and it would be very interesting to see if the region could be universally achievable. A reasonable conjecture is that the whole tradeoff region can be asymptotically approached with sufficient subpacketization and field size. In addition to the complete characterization of the repair rate region for storage, there are several other interesting open problems. OP1: The first problem is to investigate the influence of network topology, as initiated recently BIB009 for trees. All the prior work so far has been assuming a complete connectivity topology for the storage network. However, most networks of interest will have different communication capacities and sparse topologies. For these cases, communication will have a different cost and it would be interesting to formulate this as an optimization problem. OP2: While most of this work has focused on the size of communicated packets, to create these packets the amount of information that must be read from the storage nodes is large. It would be very interesting to characterize the minimum communication that must be read to repair a code. Most research on distributed storage has focused on designing MDS (or near-MDS) codes that are easily repairable. A different approach is to find ways to repair existing codes beyond the naive approach of reconstructing all the information. This is especially useful to leverage the benefits of known constructions such as reduced update complexity and efficient decoding under errors. The practical relevance of repairing a family of codes with a given structure depends on the applicability of this family in distributed storage problems. While the problem can be studied for any family of error correcting codes, two cases that are of special interest are array codes and Reed-Solomon codes. OP3 (Repairing array codes): Array codes are widely used in data storage systems BIB004 ,  , BIB005 . For the special case of evenodd codes BIB003 , a repair method that improves on the naive method of reconstructing the whole data object by a factor of 0.75 was established in BIB010 . There is still a gap from the cutset lower bound and it remains open if the minimal repair communication can be achieved if we enforce the Evenodd code structure. OP4 (Repairing Reed-Solomon codes): Another important family is Reed-Solomon codes  . A repair strategy that improves on the naive method of reconstructing the whole data object for each single failure would be directly applicable to storage systems that use Reed-Solomon codes. The repair of Reed-Solomon codes poses some challenges: since each encoded block corresponds to the evaluation of a polynomial, during repair, a partial evaluation would have to be communicated from each surviving node. This step would require a nonlinear operation and it is unclear how to create the missing evaluation from partial evaluations at the other n À 1 points. One way around this would be to use the idea of subpacketization to allow the communication of units smaller than the stored packet and stay within the framework of linear codes. OP5: A coding theory problem that has been studied in depth is that of locally decodable codes  . The issue there is to recover a symbol by reading a small subset of other (noisy) symbols. This is very similar to exact repair with the important difference that during repair the newcomer is accessing many nodes and receives small parts of symbols. In addition, repair is assuming noiseless access to other encoded symbols. Connecting exact repair to the deep theory of locally decodable codes seems like an interesting research direction. OP6: The issues of security and privacy are important for distributed storage. When coding is used, errors can be propagated in several mixed blocks through the repair process BIB011 and an error-control mechanism is required. A related issue is that of privacy of the data by information leakage to eavesdroppers during repairs  . h