Node Repair on Connected Graphs
From MaRDI portal
Publication:5088447
DOI10.1109/TIT.2022.3145824zbMATH Open1497.94176arXiv2108.00939OpenAlexW4207024543MaRDI QIDQ5088447
Publication date: 13 July 2022
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2108.00939
This page was built for publication: Node Repair on Connected Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088447)
