Provided by: Massachusetts Institute of Technology
Date Added: Jun 2011
In distributed storage systems, Maximum Distance Separable (MDS) erasure codes are well-known coding schemes that can offer maximum reliability for a given storage overhead. Consider a scenario where a file of size M is to be stored in n distributed storage nodes. The file is split into k equal parts of size M=k and stored in the first k storage nodes, also known as systematic nodes. The remaining (n-k) nodes, known as parity nodes or non-systematic nodes, store data of the same size, i.e., M/k, adding redundancy to protect from failure of storage nodes. The parity nodes are designed so that a failure of up to (n-k) storage nodes can be tolerated, i.e., the original file can be completely recovered from the data stored at any k nodes out of the original n nodes.