Non-MDS CODES WITH OPTIMAL REPAIR EFFICIENCY FOR DISTRIBUTED STORAGE SYSTEMS

Abstract

In the distributed storage systems, it is important to import as small amount of information as possible to repair the failed node when a storage node fails. The previous MDS codes with optimal repair efficiency have substantially high encoding and decoding complexity. Therefore, this paper suggests the non-MDS codes with optimal repair efficiency and substantially lower encoding and decoding complexity. The suggested non-MDS codes have the systematic and rateless property. We derive the mathematical formula for the probability distribution of the locality since the locality can be used as the performance metric of the repair efficiency for the distributed storage systems. In order to find the degree distribution of the suggested non-MDS codes, we construct the optimization problem that minimizes the average locality with the constraint that is closely related to the data reliability. The solution of the optimization problem corresponds to the degree distribution that optimizes the average locality and we name as Minimum Locality Distribution(MLOD). It is shown that the suggested non-MDS codes have lower average locality than other codes with the degree distributions such as Robust-Soliton distribution(RSD) and Asteris distribution(AD). It is shown that the suggested non-MDS codes have sufficiently lower probability that the locality cannot be defined than other codes whose average degree is of constant order. It is shown that the suggested non-MDS codes have sufficiently lower complexity than the previous MDS codes. It is shown that the suggested non-MDS codes can ensure the reliable decoder performance for properly chosen coefficient of the average degree and the sufficiently large finite field size.