We consider regenerating codes in distributed storage systems where connections between the nodes are constrained by a graph. In this problem, the failed node downloads the information stored at a subset of vertices of the graph for the purpose of recovering the lost data. Compared to the standard setting, regenerating codes on graphs address two additional features. The repair information is moved across the network, and the cost of node repair is determined by the graphical distance from the helper nodes to the failed node. Accordingly, the helpers far away from the failed node may be expected to contribute less data for repair than the nodes in the neighborhood of that node. We analyze regenerating codes with nonuniform download for repair on graphs. Moreover, in the process of repair, the information moved from the helpers to the failed node may be combined through intermediate processing, reducing the repair bandwidth. We derive lower bounds for communication complexity of node repair on graphs, including repair schemes with nonuniform download and intermediate processing, and construct codes that attain these bounds. Additionally, some of the nodes may act as adversaries, introducing errors into the data moved in the network. For repair on graphs in the presence of adversarial nodes, we construct codes that support node repair and error correction in systematic nodes.

We study regenerating codes in heterogeneous distributed storage systems including the node repair problem in graphically constrained architectures. We show that the communication cost of repair can be decreased by downloading the amounts of data controlled by the distance of the helper to the failed node. At the same time, given the flexible choice of the repair degree, the optimal repair cost can always be attained by relying on uniform downloads. We also give a construction of codes that attain a general version of the cutset bound for heterogeneous and graphically constrained systems. The codes we construct also support data combining at intermediate nodes during repair.

Node repair on graphs is a recent variation of the distributed storage model, where connections between the storage nodes are described by a graph. Here we study this problem under the assumption that some of the nodes act as adversaries, altering the data that they store. We derive bounds on the communication complexity of repair and construct codes that support repair in the presence of adversarial nodes.

We consider the use of regenerating codes in distributed storage systems where connections between the nodes are constrained by a graph. In this setting the cost of node repair is determined by the graphical distance from the helper nodes to the failed node. In our recent work (arXiv:2108:00939) we considered the MSR case, showing that linear MSR codes are amenable to intermediate processing of the information, resulting in reduced repair bandwidth which also meets the lower bound on the minimum repair cost. Here we extend this study to the non-MSR case. We derive a lower bound on the repair bandwidth and formulate repair procedures with intermediate processing for several families of regenerating codes, with an emphasis on the recent constructions from multilinear algebra. We also consider intermediate processing for the problem of partial node repair.

We study the problem of erasure correction (node repair) for regenerating codes defined on graphs wherein the cost of transmitting the information to the failed node depends on the graphical distance from this node to the helper vertices of the graph. The information passed to the failed node from the helpers traverses several vertices of the graph, and savings in communication complexity can be attained if the intermediate vertices process the information rather than simply relaying it toward the failed node. We derive simple information-theoretic bounds on the amount of information communicated between the nodes in the course of the repair. Next we show that Minimum Storage Regenerating (MSR) codes can be modified to perform the intermediate processing, thereby attaining the lower bound on the information exchange on the graph. We also consider node repair when the underlying graph is random, deriving conditions on the parameters that support recovery of the failed node with communication complexity smaller than required by the simple relaying.

We estimate the communication complexity of node repair for regenerating codes defined on graphs. Both deterministic and random graphs are considered.