A Survey on Network Codes for Distributed Storage <s> A. Cut Analysis of Information Flow Graphs <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> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> A. Cut Analysis of Information Flow Graphs <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> BIB002
By analyzing the connectivity in the information flow graph, we can derive fundamental performance bounds about codes. In particular, if the minimum cut between s and a data collector is less than the size of original file, then we can conclude that it is impossible for the data collector to reconstruct the original file. In this section, we review the cut analysis of BIB002 and  . The setup is as follows: there are always n active storage nodes. Each node can store bits. An information flow graph (as illustrated by Fig. 5 ) corresponds to a particular evolution of the storage system after a certain number of failures/repairs. We call each failure/repair a Bstage[; in each stage, a single storage node fails and the code gets repaired by downloading bits each from any d surviving nodes. Therefore, the total repair bandwidth is ¼ d. See Fig. 5 for an example. In the initial stage, the system consists of nodes 1, 2, 3, and 4; in the second stage, the system consists of nodes 2, 3, 4, and 5. For each set of parameters ðn; d; ; ¼ dÞ, there is a family of finite or infinite information flow graphs, each of which corresponds to a particular evolution of node failures/repairs. We denote this family of directed acyclic graphs by Gðn; d; ; Þ. We restrict our attention to the symmetric setup where it is required that any k storage nodes can recover the original file, and a newcomer receives the same amount of information from each of the existing nodes. An ðn; k; d; ; Þ tuple will be feasible, if a code with storage and repair bandwidth exists. For the example in Fig. 2 , the total file has size M ¼ 4 blocks and the point (n ¼ 4, On the contrary, a standard erasure code that communicates the whole data object would correspond to ¼ 4 blocks instead. Note that n; k; d must be integers. If there is one failure, the newcomer can connect to at most all the n À 1 surviving nodes, so d n À 1 and ; ; ¼ d are the nonnegative real-valued parameters of the repair process. Theorem 1: For any ! Ã ðn; k; d; Þ, the points ðn; k; d; ; Þ are feasible and linear network codes suffice to achieve them. It is information theoretically impossible to achieve points with G Ã ðn; k; d; Þ. The threshold function Ã ðn; k; d; Þ is the following: where where d n À 1. Given ðn; k; dÞ, the minimum repair bandwidth is One important observation is that the minimum repair bandwidth ¼ d is a decreasing function of the number d of nodes that participate in the repair. While the newcomer communicates with more nodes, the size of each communicated packet becomes smaller fast enough to Fig. 1 . A distributed storage scheme uses an ð4; 2Þ erasure code in which any two nodes suffice to recover the original data. If node x 4 becomes unavailable and a new node joins the system, we need to construct new encoded blocks in x 5 . To do so, node x 5 in is connected to the d ¼ 3 active storage nodes. Assuming bits communicated from each active storage node, of interest is the minimum required. The min-cut separating the source and the data collector must be larger than M ¼ 4 blocks for regeneration to be possible. For this graph, the min-cut value is given by þ 2, implying that communicating ! 1 block is sufficient and necessary. The total repair bandwidth to repair one failure is therefore make the product d decrease. Therefore, the minimum repair bandwidth can be achieved when d ¼ n À 1. As we mentioned, code repair can be achieved if and only if the underlying information flow graph has sufficiently large min-cuts. This condition leads to the repair rates computed in Theorem 1, and when these conditions are met, simple random linear combinations will suffice with high probability as the field size over which coding is performed grows, as shown by Ho et al. BIB001 . The optimal tradeoff curve for k ¼ 5, n ¼ 10, and d ¼ 9 is shown in Fig. 6 .