Back to Search
Start Over
Centralized Multi-Node Repair Regenerating Codes.
- Source :
- IEEE Transactions on Information Theory; Jul2019, Vol. 65 Issue 7, p4180-4206, 27p
- Publication Year :
- 2019
-
Abstract
- In a distributed storage system, recovering from multiple failures is a critical and frequent task that is crucial for maintaining the system’s reliability and fault-tolerance. In this paper, we focus on the problem of repairing multiple failures in a centralized way, which can be desirable in many data storage configurations; furthermore, we show that a significant repair traffic reduction is possible. First, the fundamental trade-off between the repair bandwidth and the storage size for functional repair is established. Using a graph-theoretic formulation, the optimal tradeoff is identified as the solution to an integer optimization problem, for which a closed-form expression is derived. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR) and minimum bandwidth multi-node repair (MBMR) points, are obtained. Second, we describe a general framework for converting single erasure minimum storage regenerating codes to MSMR codes. The repair strategy for $e$ failures is similar to that for a single failure; however, certain extra requirements need to be satisfied by the repairing functions for a single failure. For illustration, the framework is applied to product-matrix codes and interference alignment codes. Furthermore, we prove that the functional MBMR point is not achievable for linear exact-repair codes. We also show that the exact-repair minimum bandwidth cooperative repair codes achieve an interior point, that lies near the MBMR point, when $k \equiv 1 \mod e$ , $k$ being the minimum number of nodes needed to reconstruct the entire data. Finally, for $k> 2e, e\mid k$ , and $e \mid d$ , where $d$ is the number of helper nodes during repair, we show that the functional repair trade-off is not achievable under exact repair, except for maybe a small portion near the MSMR point, which parallels the results for single-erasure repair by Shah et al. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 65
- Issue :
- 7
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 137099100
- Full Text :
- https://doi.org/10.1109/TIT.2019.2898660