Regenerating code (RGC)[1]
Description
An \([n,k,d,\alpha,\beta,M]_q\) Regenerating Code \(\mathcal{C}\) is an erasure correcting code that encodes \(M\) symbols from \(GF(q)\) into an \(\alpha \times n\) matrix over \(GF(q)\), with each column of the matrix treated as a coordinate of a codeword.
The code has the following properties. Any \(k\) coordinates of the codeword can be used to recover the original \(M\) symbols. Any erased coordinate, i.e., the \(\alpha\) symbols of that coordinate, can be recovered by contacting any \(d\) other coordinates and collecting \(\beta\) symbols from each one of them, where \(k \le d \le n-1\) and \(\beta \le \alpha\).
The connection of such codes to distributed storage is as follows. A file of size \(M\) symbols is encoded using the code, and the \(\alpha\) symbols of each coordinate are stored in geographically separated storage nodes. Accessing any \(k\) such nodes gives back the original file. Node failures are considered erasures in the codeword, and any such failed node can be regenerated by contacting \(d\) surviving nodes and downloading \(\beta\) symbols from each of them.
Protection
Corrects upto \(n-k\) erasures on coordinates. For standard erasure codes, like RS codes, total download bandwidth for recovery of a single node is \(k\alpha\) due to the MDS property. For regenerating codes, it is \(d\beta\) which can be significantly less. It was shown by network coding arguments that \(M \le \sum_{i=0}{k-1}\min\{\alpha,(d-i)\beta\}\). Depending on the relative values of \(\alpha\) and \(\beta\), a trade-off between storage per node and download bandwidth arises. Two extreme points of this trade-off curve are the MBR (\(\alpha = d\beta\)) and MSR (\(\alpha = (d-k+1)\beta\)) codes.Decoding
If the recovered symbols are exactly equal to the erased symbols, the repair is called an exact repair.If the recovered symbols are not exactly equal to the erased symbols but still preserve the code properties, the repair is called a functional repair.Cousin
- Locally recoverable code (LRC)— RGCs and LRCs are related via the group repair with optimal access problem [2].
Member of code lists
Primary Hierarchy
References
- [1]
- A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network Coding for Distributed Storage Systems”, IEEE Transactions on Information Theory 56, 4539 (2010) DOI
- [2]
- M. Ye and A. Barg, “Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization”, (2017) arXiv:1605.08630
Page edit log
- Adway Patra (2024-03-18) — most recent
- Victor V. Albert (2024-03-18)
Cite as:
“Regenerating code (RGC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/regenerating