Locally Repairable Codes with Two Different Locality Requirements
Geonu Kim, Jungwoo Lee · 한국통신학회논문지 · 2016
부분접속 복구 부호(Locally Repairable Code)는 분산 저장 시스템(Distributed Storage System)의 효율적인 노드 복구(repair)를 위한 부호로서, 부분접속수(locality), 즉 복구 과정에서 사용되는 노드의 개수를 작게 함으로써 복구의 효율성을 높이는 것을 목적으로 한다. 본 논문에서는 각 노드의 부분접속수가 서로 다른 값으로 규정되는 상황을 다룬다. 다중 부분접속수에 대한 기존의 연구 결과를 ( $r,{\delta}$ )-부분접속수의 경우로 확장하여, 서로 다른 두 부분접속수로 규정되는 부호의 최소 거리 상계 및 이를 달성하는 최적 부호의 설계를 제시한다. 제안되는 상계는 기존의 연구와 달리 다중 부분접속수의 개수가 두 개로 제한되지만, 부호의 부분접속수가 정확하게 주어지지 않고 상한으로만 주어지는 보다 일반적인 경우에 직접 적용 가능하다. Locally repairable codes (LRCs) constitute an important class of codes for distributed storage, where repair efficiency is a key metric of system performance. In LRCs, efficient repair is achieved by small locality-number of nodes participating in the repair process. In this paper, we focus on situations where different locality is required for different nodes. We present a non-trivial extension of the recent results on multiple (or unequal) localities to the $r,{\delta}$ -locality case. A new Singleton-type minimum distance upper bound is derived and an optimal code construction is provided. While the result is limited to the case of only two different localities, it should be noted that it can be directly applied to the more general case where the localities are specified not exactly but by upper limits.