Cooperative Repair: Constructions of Optimal MDS Codes for All Admissible Parameters
Cooperative Repair: Constructions of Optimal MDS Codes for All Admissible Parameters
复制标题
DOI：
10.1109/tit.2018.2856206
复制
发表时间：
2018-01
影响因子：
2.5
通讯作者：
Min Ye;A. Barg
中科院分区：
文献类型：
--
作者：
Min Ye;A. Barg
分布式存储系统中多个节点修复的两个广泛研究的模型是集中修复和坐标修复，假设所有失败的节点都在一个位置重新创建在维修带宽中，它们之间交换的数据数量是我们的第一个结果，我们证明了对合作维修的最小带宽的下限。以前模型下的最大距离（MDS）代码在后来的一个型号下也具有最佳的带宽结果，我们更精确地给出了所有可能的参数的MDS代码的明确构造。 ，k）$ f $ a $ f $ size $ | f | f | \ ge（d+1-k）n $的$ MDS代码，可以从任何$ d $ helper节点中最佳维修任何$ h $擦除。我们的代码在第一轮中涉及两轮通信，每个节点都会从辅助节点下载信息，而在第二轮中，每个节点都会下载失败的节点。带宽使用最少数量的回合。
Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. As our first result, we prove a lower bound on the minimum bandwidth of cooperative repair. We also show that the cooperative model is stronger than the centralized one, in the sense that any maximum distance separable (MDS) code with optimal repair bandwidth under the former model also has optimal bandwidth under the latter one. These results were previously known under the additional “uniform download” assumption, which is removed in our proofs. As our main result, we give explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any $n,k,h,d$ such that $2\le h \le n-d\le n-k$ we construct $(n,k)$ MDS codes over the field $F$ of size $|F|\ge (d+1-k)n$ that can optimally repair any $h$ erasures from any $d$ helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the other failed nodes. This implies that our codes achieve the optimal repair bandwidth using the smallest possible number of rounds.