A novel construction of low-complexity MDS codes with optimal repair capability for distributed storage systems

作     者：Guan, Sheng Kan, Haibin Wang, Xin 

作者机构：Shanghai Key Laboratory of Intelligent Information Processing Fudan-Zhongan Joint Lab of Blockchain and Information Security School of Computer Science Fudan University Shanghai200433 China School of Information Science and Engineering Fudan University Shanghai200433 China 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2017年

核心收录：

主　　题：Bandwidth 

摘      要：Maximum-distance-separable (MDS) codes are a class of erasure codes that are widely adopted to enhance the reliability of distributed storage systems (DSS). In (n, k) MDS coded DSS, the original data are stored into n distributed nodes in an efficient manner such that each storage node only contains a small amount (i.e., 1/k) of the data and a data collector connected to any k nodes can retrieve the entire data. On the other hand, a node failure can be repaired (i.e., stored data at the failed node can be successfully recovered) by downloading data segments from other surviving nodes. In this paper, we develop a new approach to construction of simple (5, 3) MDS codes. With judiciously block-designed generator matrices, we show that the proposed MDS codes have a minimum stripe size α = 2 and can be constructed over a small (Galois) finite field F4 of only four elements, both facilitating low-complexity computations and implementations for data storage, retrieval and repair. In addition, with the proposed MDS codes, any single node failure can be repaired through interference alignment technique with a minimum data amount downloaded from the surviving nodes;i.e., the proposed codes ensure optimal exact-repair of any single node failure using the minimum bandwidth. The low-complexity and all-node-optimal-repair properties of the proposed MDS codes make them readily deployed for practical DSS. Copyright © 2017, The Authors. All rights reserved.