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.
분산 저장 시스템에서 저장 노드가 소실되었을 때 최소한의 정보를 이용하여 소실된 노드를 복구해야 한다. 기존의 엠디에스 부호는 복구 효율성이 최적이지만 복잡도가 매우 높다. 따라서 본 연구논문은 최적의 복구 효율성을 가지면서 복잡도가 낮은 논 엠디에스 부호를 제안한다. 제안한 논 엠디에스 부호는 체계적이며 레이트리스 성질을 가진다. 분산 저장 시스템에서 부분접속수가 복구 효율성의 성능 척도로 활용될 수 있으므로 부분접속수의 확률 분포에 관한 수학 공식을 유도한다. 제안한 논 엠디에스 부호의 차수 분포를 찾기 위해 데이터 신뢰도와 밀접히 관련된 제한 조건을 가지면서 평균 부분접속수를 최소화하는 최적화 문제를 설계한다. 최적화 문제의 해는 평균 부분접속수를 최적화하는 차수 분포에 대응된다. 이 차수 분포를 최소 부분접속수 분포라고 이름을 붙인다. 최소 부분접속수 분포가 다른 차수 분포보다 낮은 평균 부분접속수를 가짐을 보인다. 제안한 논 엠디에스 부호가 부분접속수가 정의되지 못할 확률이 평균 차수가 상수 형태인 다른 부호보다 현저히 낮음을 보인다. 제안한 논 엠디에스 부호가 기존의 엠디에스 부호보다 복잡도가 매우 낮음을 보인다. 평균 차수의 계수가 적당한 값을 가지고 유한체 크기가 충분히 클 때 제안한 논 엠디에스 부호가 신뢰도 있는 복호기 성능을 보장함을 보인다.
