A Survey on Network Codes for Distributed Storage <s> II. MODEL I: FUNCTIONAL REPAIR <s> Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node. <s> BIB001 </s> A Survey on Network Codes for Distributed Storage <s> II. MODEL I: FUNCTIONAL REPAIR <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
As shown in BIB002 , the functional repair problem can be represented as multicasting over an information flow graph. The information flow graph represents the evolution of information flow as nodes join and leave the storage network (see also  for a similar construction). Fig. 5 gives an example of an information flow graph. In this graph, each storage node is represented by a pair of nodes x i in and x i out connected by an edge whose capacity is the storage capacity of the node. There is a virtual source node s corresponding to the origin of the data object. Suppose initially we store a file of size M ¼ 4 blocks at four nodes, where each node stores ¼ 2 blocks and the file can be reconstructed from any two nodes. Virtual sink nodes called data collectors connect to any k node subsets and ensure that the code has the MDS property (that any k out of n suffices to recover). Suppose storage node 4 fails, then the goal is to create a new storage node, node 5, which communicates the minimum amount of information and then stores ¼ 2 blocks. This is represented in Fig. 5 by the unit-capacity edges x 1 out x 5 in , x 2 out x 5 in , and x 3 out x 5 in that enter node x 5 in . The functional repair problem for distributed storage can be interpreted as a multicast communication problem defined over the information flow graph, where the source s wants to multicast the file to the set of all possible data collectors. For multicasting, it is known that the maximum multicast rate is equal to the minimum-cut capacity separating the source from a receiver and it can be achieved using linear network coding BIB001 . Since the current problem can be viewed as a multicast problem, the fundamental limit can be characterized by the min-cuts in the information flow graph and network coding provides effective constructive solutions. One complication is that since the number of failures/repairs is unbounded, the resulting information flow graph can grow unbounded in size. Hence, we have to deal with cuts, flows, and network codes in graphs that are potentially infinite. In Section II-A, we present the cut analysis of information flow graphs BIB002 ,  . In Section II-B, we discuss the two extreme points corresponding to minimum repair bandwidth and minimum storage cost.