#
An Improved Sub-Packetization Bound for

Minimum Storage Regenerating Codes^{†}^{†}thanks: The material in this paper will be presented in part at the IEEE International Symposium on Information Theory (ISIT 2013), Istanbul, Turkey, July 2013.

###### Abstract

Distributed storage systems employ codes to provide resilience to failure of multiple storage disks.
Specifically, an MDS code stores symbols in disks such that the overall system is tolerant to a failure of up to disks. However, access to at least 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 .
MDS array codes have the potential to repair a single erasure using a fraction 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 , what is the minimum vector-length or sub-packetization factor required to achieve this optimal fraction?
For *exact recovery* of systematic disks in an MDS code of low redundancy, i.e. , the best known explicit codes [1] have a sub-packetization factor which is exponential in . It has been conjectured [2] that for a fixed number of parity nodes, it is in fact necessary for to be exponential in . In this paper, we provide a new log-squared converse bound on for a given ,
and prove that , for an arbitrary number of parity nodes , where .

## I Introduction

Maximum Distance Separable (MDS) codes are ubiquitous in distributed storage systems [3] since they provide the maximum resilience to erasures for a given redundancy. We define an storage system as consisting of nodes or disks of capacity (data) units, and storing a total of data units. When the units in each disk constitute a symbol in an MDS (array) code, the system is immune to an erasure of up to disks. Failure of a single disk at a time occurs most frequently in practice. The objective is to quickly and efficiently recover the data in an erased disk. A naïve way is to reconstruct the entire data by using any of the surviving disks and recover the data in the lost node. However, as can be seen in Example 1, transmission of units to the repair center is not necessary to recover the loss of data units; transmission of units is sufficient. Dimakis et al. [4] formalized this problem of efficient repair and proved that the bandwidth or the amount of transmitted data required to recover a single disk erasure in an MDS code is lower bounded by

where all the surviving disks transmit a fraction of their data.