Event
Ph.D. Dissertation Defense: Adway Patra
Tuesday, July 22, 2025
4:00 p.m.
AVW 2168
Souad Nejjar
301 405 8135
snejjar@umd.edu
ANNOUNCEMENT: Ph.D. Dissertation Defense
Name: Adway Patra
Committee:
Date/time: Tuesday, July 22, 2025 at 4:00 PM
Location: AVW 2168
Title: CODES FOR DATA RETRIEVAL AND NODE REPAIR IN GRAPHICAL NETWORKS
Abstract: This dissertation investigates the problem of efficient data recovery in distributed storage systems relying 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 the nodes in the course of the repair. Moreover, we show that the lower bound on the information transmission is achievable by modifying codes from the class of Minimum Storage Regenerating (MSR) codes to perform 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 a lower 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 on graphs. 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 node repair and error correction.
