An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes

作者：Goparaju Sreechakra^*; Tamo Itzhak; Calderbank Robert

来源：IEEE Transactions on Information Theory, 2014, 60(5): 2770-2779.

DOI：10.1109/TIT.2014.2309000

• distributed storage
• error correction codes
• interference alignment
• sub-packetization

Distributed storage systems employ codes to provide resilience to failure of multiple storage disks. In particular, an (n, k) maximum distance separable (MDS) code stores k symbols in n disks such that the overall system is tolerant to a failure of up to n - k disks. However, access to at least k disks is still required to repair a single erasure. To reduce repair bandwidth, array codes are used where the stored symbols or packets are vectors of length l. The MDS array codes have the potential to repair a single erasure using a fraction 1/(n - k) of data stored in the remaining disks. We introduce new methods of analysis, which capitalize on the translation of the storage system problem into a geometric problem on a set of operators and subspaces. In particular, we ask the following question: for a given (n, k), what is the minimum vector-length or subpacketization factor l required to achieve this optimal fraction? For exact recovery of systematic disks in an MDS code of low redundancy, i.e., k/n > 1/2, the best known explicit codes have a subpacketization factor l, which is exponential in k. It has been conjectured that for a fixed number of parity nodes, it is in fact necessary for l to be exponential in k. In this paper, we provide a new log-squared converse bound on k for a given l, and prove that k <= 2 log(2) l (log(delta) l + 1), for an arbitrary number of parity nodes r = n - k, where delta = r/(r - 1).

• 出版日期2014-5