When Can Helper Node Selection Improve Regenerating Codes? Part II: An Explicit Exact-Repair Code Construction.
Imad Ahmad, Chih-Chun Wang · arXiv (Cornell University) · 2016
Part I of this work answered the following fundamental question: Under and only under what (n,k,d) values does proactively choosing the helper nodes improve the storage-bandwidth tradeoff of regenerating codes (RCs)? A critical component of the achievability results in Part I is a low-complexity helper selection solution, termed the family helper selection (FHS) scheme. In Part I, FHS was proved to be optimal or weakly optimal (depending on the underlying scenario) based on the assumption that as long as the minimum min-cut value of FHS is no less than the file size, we can always find a distributed storage code that can reconstruct the original file. This work relaxes this assumption by providing an exact-repair code construction that attains the minimum-bandwidth-regenerating (MBR) point of FHS, previously calculated/predicted only by the min-cut analysis in Part I. As an outcome, for the MBR points, FHS is indeed optimal or weakly optimal under various scenarios. In addition to closing the loop of the graph-based study in Part I, the proposed construction can also be viewed as a generalization of the existing fractional repetition (FR) codes. FR codes are exact-repair codes that admit the highly-desirable repair-by-transfer property. However, the unique construction of FR codes limits its application to a restricted set of (n,k,d) system parameters. In contrast, our new construction, termed the generalized FR (GFR) codes, can be applied to arbitrary (n,k,d) values. Our GFR codes retain most of the practical benefits of FR codes, i.e., being exact-repair and being almost repairable-by-transfer.