When and By How Much Can Helper Node Selection Improve Regenerating Codes?
arXiv:1401.4509 · doi:10.1109/ALLERTON.2014.7028491
Abstract
Regenerating codes (RCs) can significantly reduce the repair-bandwidth of distributed storage networks. Initially, the analysis of RCs was based on the assumption that during the repair process, the newcomer does not distinguish (among all surviving nodes) which nodes to access, i.e., the newcomer is oblivious to the set of helpers being used. Such a scheme is termed the blind repair (BR) scheme. Nonetheless, it is intuitive in practice that the newcomer should choose to access only those "good" helpers. In this paper, a new characterization of the effect of choosing the helper nodes in terms of the storage-bandwidth tradeoff is given. Specifically, answers to the following fundamental questions are given: Under what conditions does proactively choosing the helper nodes improve the storage-bandwidth tradeoff? Can this improvement be analytically quantified? This paper answers the former question by providing a necessary and sufficient condition under which optimally choosing good helpers strictly improves the storage-bandwidth tradeoff. To answer the latter question, a low-complexity helper selection solution, termed the family repair (FR) scheme, is proposed and the corresponding storage/repair-bandwidth curve is characterized. For example, consider a distributed storage network with 60 total number of nodes and the network is resilient against 50 node failures. If the number of helper nodes is 10, then the FR scheme and its variant demonstrate 27% reduction in the repair-bandwidth when compared to the BR solution. This paper also proves that under some design parameters, the FR scheme is indeed optimal among all helper selection schemes. An explicit construction of an exact-repair code is also proposed that can achieve the minimum-bandwidth-regenerating point of the FR scheme. The new exact-repair code can be viewed as a generalization of the existing fractional repetition code.
35 pages, 10 figures, submitted to IEEE Transactions on Information Theory on September 04, 2014
References in corpus (5)
- Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
- Distributed Data Storage with Minimum Storage Regenerating Codes - Exact and Functional Repair are Asymptotically Equally Efficient
- On the Existence of Optimal Exact-Repair MDS Codes for Distributed Storage
- Fractional Repetition Codes for Repair in Distributed Storage Systems
- When and By How Much Can Helper Node Selection Improve Regenerating Codes?