Permutation Codes: Optimal Exact-Repair of a Single Failed Node in MDS Code Based Distributed Storage Systems

It is well known that maximum distance separable (MDS) codes are an efficient means of storing data in distributed storage systems, since they provide optimal tolerance against failures (erasures) for a fixed amount of storage. A (n, k) code can be used in a distributed storage system with n disks, each having a storage capacity of 1 unit, to store k units of information, where n> k. If the code used is maximum distance separable, then the storage system can tolerate up to (n − k) disk failures (erasures). The focus of this paper is the design of a MDS code with the additional property that a single disk failure can be repaired with optimal repair bandwidth, i.e., the amount of data to be downloaded for recovery of the failed node. Previously, a lower bound of n−1 n−k units has been established by Dimakis et. al, on the repair bandwidth for a single node failure in an (n, k) MDS code based storage system, where each of the n disks store 1 unit. While the reference by Dimakis et. al., established a lower bound on the repair bandwidth, existence of codes achieving this lower bound for arbitrary (n, k) have only been established in an asymptotic manner, in the limit of arbitrarily large storage capacities. While finite code constructions achieving this lower bound have been provided previously for k ≤ max(n/2, 3), the question of existence of finite codes for arbitrary values of (n, k) achieving the lower bound remained open. In this paper, we provide the first known construction of a finite code for arbitrary (n, k), which can repair a single failed systematic node by downloading exactly n−1 n−k units of data. The codes, which are optimally efficient in terms of a metric known as repair bandwidth, are based on permutation matrices and hence termed Permutation Codes. We also show that our code has a simple repair property which enables efficiency, not only in terms of the amount of repair bandwidth, but also in terms of the amount of data accessed on the disk. I