An Exponential Lower Bound on the Sub-Packetization of MSR Codes

摘要

An ( n k ) -vector MDS code is a F -linear subspace of ( F ) n (for some field F ) of dimension k , such that any k (vector) symbols of the codeword suffice to determine the remaining r = n ? k (vector) symbols. The length 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 r 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 of at least r k r . Our main result is an almost tight lower bound showing that for an MSR code, one must have exp ( ( k r )) . Previously, a lower bound of exp ( k r ) , and a tight lower bound for a restricted class of optimal access MSR codes, were known. Our work settles a key question concerning MSR codes that has received much attention, with a short proof hinging on one key definition that is somewhat inspired by Galois theory.