A Survey on Network Codes for Distributed Storage <s> IV. MODEL III: EXACT REPAIR OF THE SYSTEMATIC PART <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> IV. MODEL III: EXACT REPAIR OF THE SYSTEMATIC PART <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> BIB002
In this section, we review the constructive scheme given in  , which gives a construction of systematic ðn; kÞ-MDS codes for 2k n that achieves the minimum repair bandwidth when repairing from k þ 1 nodes. The scheme is illustrated in Fig. 11 . Let F denote the finite field where the code is defined in. In Fig. 11 , x 2 F 2k is a vector consisting of the 2k original information symbols. Each node stores two symbols x T u i and x T v i . The vectors fu i g do not change over time but fv i g change as the code repairs. We maintain the invariant property that the 2n length-2k vectors fu i ; v i g form an ð2n; 2kÞ-MDS code; that is, any 2k vectors in the set fu i ; v i g have full rank 2k. This certainly implies that the n nodes form an ðn; kÞ-MDS code. We initialize the code using any ð2n; 2kÞ systematic MDS code over F. Now we consider the situation of a repair. Without loss of generality, suppose node n failed and is repaired by accessing nodes 1; . . . ; k þ 1. As illustrated in Fig. 11 , the replacement node downloads i x T u i þ i x T v i from each node of f1; . . . ; k þ 1g. Using these k þ 1 downloaded symbols, the replacement node computes two symbols x T u n and x T v 0 n as follows: Note that v 0 n is allowed to be different from v n ; the property that we maintain is that the repaired code continues to be an ð2n; 2kÞ-MDS code. Here f i ; i ; i g and v 0 n are the variables that we can control. The following theorem shows that we can choose these variables so that BIB002 and BIB001 are satisfied and the repaired code continues to be an ð2n; 2kÞ-MDS code. Theorem 4  : Let F be a finite field whose size is greater than Fig. 11 . Illustration of the scheme in  .