Node Repair on Connected Graphs
Node Repair on Connected Graphs
复制标题
DOI：
10.1109/tit.2022.3145824
复制
发表时间：
2021-08
影响因子：
2.5
通讯作者：
Adway Patra;A. Barg
中科院分区：
文献类型：
--
作者：
Adway Patra;A. Barg
我们研究了图表上定义的再生代码的擦除校正问题（节点修复），其中将信息传输到失败节点的成本取决于图形距离从该节点到图形的辅助顶点的图形距离。从帮助者传递给失败节点的信息遍历图的几个顶点，并且如果中间顶点处理信息，而不是简单地将其传达给失败的节点，则可以获得通信复杂性的节省。我们得出了简单的信息理论界限，内容涉及维修过程中节点之间传达的信息量。接下来，我们表明可以修改最小存储再生（MSR）代码以执行中间处理，从而在图表上获得信息交换的下限。当基础图是随机的时，我们还考虑节点修复，从而在参数上得出条件，这些参数支持失败节点的恢复，而通信复杂性比简单继电器所要求的小。
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.