A Survey on Network Codes for Distributed Storage <s> Dimakis et al.: A Survey on Network Codes for Distributed Storage <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> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> Dimakis et al.: A Survey on Network Codes for Distributed Storage <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> BIB002 </s> A Survey on Network Codes for Distributed Storage <s> Dimakis et al.: A Survey on Network Codes for Distributed Storage <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> Dimakis et al.: A Survey on Network Codes for Distributed Storage <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 </s> A Survey on Network Codes for Distributed Storage <s> Dimakis et al.: A Survey on Network Codes for Distributed Storage <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> BIB005
where u and v are 3-D vectors. Note that the dimension of the null space of v is 2 and the null vector v ? is an eigenvector of A, i.e., Av ? ¼ v ? . This motivates the following structure: where v i 's are 3-D linearly independent vectors and so are u i 's. The values of the i 's, i 's, and i 's can be arbitrary nonzero values. For simplicity, we consider the simple case where the v i 's are orthonormal, although these need not be orthogonal, but only linearly independent. We then see that 8i ¼ 1; 2; 3 Importantly, notice that v 1 is a common eigenvector of the B i 's and C i 's, while simultaneously ensuring that the vectors of A i v 1 are linearly independent. Hence, setting v i ¼ v 1 for all i, it is possible to achieve simultaneous interference alignment while also guaranteeing the decodability of the desired signals. On the other hand, this structure also guarantees exact repair for b and c. We use v 2 for exact repair of b. It is a common eigenvector of the C i 's and A i 's, while ensuring Parity nodes can be repaired by drawing a dual relationship with systematic nodes. The procedure has two steps. The first is to remap parity nodes with a 0 , b 0 , and c 0 , respectively. Systematic nodes can then be rewritten in terms of the prime notations where the newly mapped encoding matrices ðA 0 i ; B 0 i ; C i Þ's are defined as With this remapping, one can dualize the relationship between systematic and parity node repair. Specifically, if all of the A 0 i 's, B 0 i 's, and C 0 i 's are elementary matrices and form a similar code structure as in BIB001 , exact repair of the parity nodes becomes transparent. It was shown that a special relationship between ½u 1 ; u 2 ; u 3 and ½v 1 ; v 2 ; v 3 through the correct choice of ð i ; i ; i Þ's can also guarantee the dual structure of (10) BIB003 . Fig. 10 shows a numerical example for exact repair of systematic node 1 [ Fig. 10(a) ] and parity node 1 [ Fig. 10(b) ] where ½v 1 ; v 2 ; v 3 ¼ ½2; 2; 2; 2; 3; 1; 2; 1; 3. This example illustrates the code structure that generalizes the code introduced in BIB004 . See BIB003 for details. This generalized code structure allows for a much larger design space for exact repair. Notice that the projection vector solution for systematic node repair is simple: Note that this choice enables simultaneous interference alignment, while guaranteeing the decodability of a. Notice that ðb 1 ; b 2 ; b 3 Þ and ðc 1 ; c 2 ; c 3 Þ are aligned into b 1 þ b 2 þ b 3 and c 1 þ c 2 þ c 3 , respectively, while three equations associated with a are linearly independent. The dual structure also guarantees exact repair of parity nodes. Importantly, we have chosen code parameters from the generalized code structure of BIB003 such that parity node repair is quite simple. As shown in Fig. 10(b) , downloading only the first equation from each survivor node ensures exact repair. Notice that the five downloaded equations contain only five unknown variables of ða 0 1 ; a 0 2 ; a 0 3 ; b 0 1 ; c 0 1 Þ and three equations associated with a 0 are linearly independent. Hence, we can successfully recover a 0 . It has been shown in BIB003 that this alignment technique can be easily generalized to arbitrary ðn; k; dÞ where n ! 2k and d ! 2k À 1. Suppose the old code specified by fu i ; v i g is an ð2n; 2kÞ-MDS code defined over F. When node n fails, there exists an assignment of the variables f i ; i ; i g such that BIB005 and BIB002 are satisfied and the repaired code continues to be an ð2n; 2kÞ-MDS code. Corollary 1 [A Systematic ðn; kÞ-MDS Code]: The above scheme gives a construction of systematic ðn; kÞ-MDS codes for 2k n that achieves the minimum repair bandwidth when repairing from k þ 1 nodes. Proof: Consider n ! 2k. Note that in the above scheme, we can initialize the code fu 1 ; . . . ; u n ; v 1 ; . . . ; v n g with any ð2n; 2kÞ-MDS code. In particular, we can use a systematic code and assign the 2k systematic code vectors to fu 1 ; . . . ; u 2k g. Since fu 1 ; . . . ; u n g do not change over time, the code remains a systematic ð2n; 2kÞ-MDS code. Thus, the n nodes form a systematic ðn; kÞ-MDS code. The code repairs a failure by downloading k þ 1 blocks from d ¼ k þ 1 nodes, with the total file size M ¼ 2k, achieving the cutset bounds derived in Section II. h