# 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

## Decoding

## Parents

## Children

- Determinant code
- Minimum-bandwidth regenerating (MBR) code — MBR codes are extreme points in the storage-bandwidth trade-off curve and are characterised by \(\alpha = d\beta\).
- Minimum-storage regenerating (MSR) code — MSR codes are extreme points in the storage-bandwidth trade-off curve and are characterised by \(\alpha = (d-k+1)\beta\).
- Product-matrix (PM) code

## Cousin

- Locally recoverable code (LRC) — RGCs and LRCs are related via the group repair with optimal access problem [2].

## References

- [1]
- A. G. Dimakis et al., “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