TU4.R3.1

Constructions of Binary MDS Array Codes with Optimal Cooperative Repair Bandwidth

Lei Li, Department of Computer Science and Engineering, Shanghai Jiao Tong University, China; Xinchun Yu, Institute of Data and Informtion, Shenzhen International Graduate School of Tsinghua University, China; Chenhao Ying, Department of Computer Science and Engineering, Shanghai Jiao Tong University, China; Liang Chen, Yuanyuan Dong, Alibaba Group, China; Yuan Luo, Department of Computer Science and Engineering, Shanghai Jiao Tong University, China

Session:
Codes for Storage 4

Track:
13: Coding for Computation and Storage

Location:
Ypsilon IV-V-VI

Presentation Time:
Tue, 9 Jul, 16:05 - 16:25

Session Chair:
P Vijay Kumar, Indian Institute of Science Bangalore
Abstract
Erasure codes are widely implemented in distributed storage systems to provide high fault tolerance with small storage overhead. Maximum distance separable codes are an common choice as they achieve the optimal tradeoff between fault tolerance and storage overhead. In this paper, we focus on the repair of multiple erasures of binary MDS array codes. Specifically, we present constructions of binary MDS array codes with optimal cooperative repair bandwidth by stacking multiple Blaum-Roth code instances whose ``evaluation points'' are judiciously designed. The constructed array codes with length n and dimension k can achieve the optimal cooperative repair bandwidth for 2 <= h <= n-k and k+1 <= d <= n-h where h and d are the numbers of failed nodes and helper nodes, respectively. As the codes are constructed on a special polynomial ring over binary field, computation operations involved in nodes repair and file reconstruction for these codes are only XORs and cyclic shifts. Moreover, due to the inherent parallel structure of the codes, both the encoding and decoding procedures can be finished in parallel, speeding up the computing process.
Resources