text: An @math -vector MDS code is a @math -linear subspace of @math (for some field @math ) of dimension @math , such that any @math (vector) symbols of the codeword suffice to determine the remaining @math (vector) symbols. The length @math of each codeword symbol is called the sub-packetization of the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading @math field elements (which is known to be the least possible) from each of the other symbols. MSR codes are attractive for use in distributed storage systems, and by now a variety of ingenious constructions of MSR codes are available. However, they all suffer from exponentially large sub-packetization @math . Our main result is an almost tight lower bound showing that for an MSR code, one must have @math . Previously, a lower bound of @math , and a tight lower bound for a restricted class of "optimal access" MSR codes, were known. Our work settles a central open question concerning MSR codes that has received much attention. Further our proof is really short, hinging on one key definition that is somewhat inspired by Galois theory.
  @cite_0: Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (node) failures. A node is said to have capacity l over some field F, if it can store that amount of symbols of the field. An (n, k, l) MDS code uses n nodes of capacity l to store k information nodes. The MDS property guarantees the resiliency to any n-k node failures. An optimal bandwidth (respectively, optimal access) MDS code communicates (respectively, accesses) the minimum amount of data during the repair process of a single failed node. It was shown that this amount equals a fraction of 1 (n - k) of data stored in each node. In previous optimal bandwidth constructions, l scaled polynomially with k in codes when the asymptotic rate is less than 1. Moreover, in constructions with a constant number of parities, i.e., when the rate approaches 1, l is scaled exponentially with k. In this paper, we focus on the case of linear codes with linear repair operations and constant number of parities n - k = r, and ask the following question: given the capacity of a node l what is the largest number of information disks k in an optimal bandwidth (respectively, access) (k + r, k, l) MDS code? We give an upper bound for the general case, and two tight bounds in the special cases of two important families of codes. The first is a family of codes with optimal update property, and the second is a family with optimal access property. Moreover, the bounds show that in some cases optimal-bandwidth codes have larger k than optimal-access codes, and therefore these two measures are not equivalent.
  @cite_15: MDS codes are erasure-correcting codes that can correct the maximum number of erasures given the number of redundancy or parity symbols. If an MDS code has r parities and no more than r erasures occur, then by transmitting all the remaining data in the code one can recover the original information. However, it was shown that in order to recover a single symbol erasure, only a fraction of 1 r of the information needs to be transmitted. This fraction is called the repair bandwidth (fraction). Explicit code constructions were given in previous works. If we view each symbol in the code as a vector or a column, then the code forms a 2D array and such codes are especially widely used in storage systems. In this paper, we ask the following question: given the length of the column l, can we construct high-rate MDS array codes with optimal repair bandwidth of 1 r, whose code length is as long as possible? In this paper, we give code constructions such that the code length is (r + l)log r l.
  @cite_10: In this paper, we revisit the problem of finding the longest systematic-length @math for a linear minimum storage regenerating (MSR) code with optimal repair of only systematic part, for a given per-node storage capacity @math and an arbitrary number of parity nodes @math . We study the problem by following the geometric analysis of linear subspaces and operators. First, a simple quadratic bound is given, which implies that @math is the largest number of systematic nodes in the scenario. Second, an @math -based-log bound is derived, which is superior to the upper bound on log-base @math in the prior work. Finally, an explicit upper bound depending on the value of @math is introduced, which further extends the corresponding result in the literature.
  @cite_24: 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 log2 I(logδ l + 1), for an arbitrary number of parity nodes r = n - k, where δ = r (r - 1).
summary: Turning to known lower bounds on @math , a weak bound of @math was shown via a combinatorial argument in @cite_0 . Using an elegant linear independence and partitioning argument, the following bound is proven in @cite_24 : (This was slightly improved in @cite_10 , but the improvement is tiny for the case when @math which is our focus.) The bound implies a lower bound on sub-packetization of @math . Even for the case @math , it was not known if one can achieve sub-packetization smaller than @math . Our Theorem now rules out this possibility. We conjecture that our bound can be improved to @math which will show that the construction in @cite_15 is exactly tight.