Codes for Data Retrieval and Node Repair in Graphical Networks

Abstract

This dissertation investigates the problem of efficient data recovery in distributed storage systemsrelying on erasure codes, when the connections between individual nodes of the system are constrained by a connected graph. In this model, when a node fails, i.e., the data stored in it becomes lost or unavailable, the other surviving nodes in the network send information, which is a function of their local stored data, along the edges of the graph to repair the failed node. We show that savings in communication complexity can be attained if the intermediate vertices along the path process the information rather than simply relay it toward the failed node.

We derive information-theoretic bounds on the amount of information communicated between thenodes in the course of the repair. Moreover, we show that the lower bound on the information exchange is achievable by modifying codes from the class of Minimum Storage Regenerating (MSR) codes to per- form intermediate processing. Our analysis extends to both deterministic connected graphs and random graphs, where we derive conditions on the system parameters that support recovery of the failed node with complexity lower than relaying.

In the second part of the thesis, we extend our study to general regenerating codes. We derive alower bound on the repair bandwidth and formulate repair procedures with intermediate processing for several algebraic families of regenerating codes. We also address the problem of data retrieval in the communication-constrained setting, deriving lower bounds and optimal protocols.

In the final part, we consider regenerating codes with nonuniform contribution for node repair ongraphs. We begin with deriving information-theoretic lower bounds for communication complexity of repair and propose code constructions and repair schemes that attain these bounds. As the main conclusion, we show that a combination of nonuniform contributions and intermediate processing can further reduce the communication complexity. Additionally, for repair on graphs in the presence of adversarial nodes that can introduce errors during repair, we construct codes that support simultaneous intermediate processing and error correction.