0
$\begingroup$

Following article explains a simplified version of Erasure Coding:

Link to the article

here is the recipe:

  • Take a file of size M.
  • Split the file into k chunks, each of the same size M/k.
  • Now, apply the (n, k) code on these k chunks to get n chunks, each of the same size M/k.
  • Now the effective size is nM/k. Thus the file is expanded n/k times. We need n to be greater than or equal to k, so n/k is at least 1. If n equals k, you have just split the file and there is no coding performed.
  • Any k chunks out of the n chunks can be used to get back the file.

So this also means that the code can tolerate upto (n - k) erasures. The following figure shows this recipe being followed for a (4, 2) code.

enter image description here

Without really wondering how do actually add files, the following example illustrates one particular case of designing a (4, 2) code.

enter image description here

Lets say you have four computers (aka nodes) that you can use to store files. Instead of putting all the eggs in the same basket, you will want to spread it out and in this case, store the file twice by doing something like this:

enter image description here

where X1 is the first block of file A and X2 the second. Another way is to store the coded blocks:

enter image description here

Now if you lose nodes 1 and 3, in the case when you store uncoded blocks, X1 is lost permanently, so the file A gets corrupted. Whereas in the case when you store coded blocks, even when those two nodes fail, it is possible to recover X1 and X2 and thus A from A2 and A4. This is because A2 = X2 and A4 = X1 + 2*X2. So one can solve these equations and get back X1 and X2! Neat, isn’t it?

And my question is related to the last sentence:

How to solve these equations and get back X1 and X2 ?

We have two equations:

(1) A2 = X2 
(2) A4 = X1 + 2*X2

AFAIK: We are able to solve an equation, if the number of equations is equal or more than the number of unknown variables.

Based on this:

  1. Which ones are know and which ones are unknown in two above equations? A2 and A4 are unknown? Or X1 and X2 are unknown ?
  2. If X1 and X2 are known, then we are able to find A4 and A2 even by a single equation.so, we do not need two!
  3. If X1 and X2 are unknown, then they will be found based on A2 and A4. In this case, how is it feasible to recover the original file by two coded values A2 and A4 ?

How to solve this system of linear equations ?

It is NOT clear to me which one is known and which one is unknown:

A2 and A4 are unknown?

Or

X1 and X2 are unknown?

$\endgroup$
1
$\begingroup$

The original data are $X_1$ and $X_2$. The shares are

\begin{align*} A_1 &= X_1, \\ A_2 &= X_2, \\ A_3 &= X_1 + X_2 \\ A_4 &= X_1 + 2 X_2. \end{align*}

You store the shares $A_1$, $A_2$, $A_3$, and $A_4$ on disk, or over the internet and through the hills on someone else's disk, or buried in a tree somewhere for safekeeping. If a forest fire takes out the tree and someone else's house is washed away in a flood (or, if a malicious storage server tries to modify one of the shares and you detect it because you're using cryptography and throw that modified share away), but you still have two of the four shares, say $A_2$ and $A_4$, you can recover

\begin{align*} X_2 &= A_2, \\ X_1 &= A_4 - 2 A_2, \end{align*}

and get your original file $X_1 \mathbin\| X_2$ back.

$\endgroup$
  • $\begingroup$ Assuming instead of A2 and A4, we have A1 and A2. However, A1 and A2 are coded values, meaning that if we have X1 = A1, we do not have yet the original value of X1, but an coded value. How to retrieve the original value of X1 from coded value A1. (And the same thing about X2 and A2) Thanks $\endgroup$ – Questioner Aug 29 at 12:55
  • $\begingroup$ $A_1$ and $X_1$ are the same value. $\endgroup$ – Squeamish Ossifrage Aug 29 at 14:26
  • $\begingroup$ I know that, and that's thing is not clear to me. Why? because X1 is non-coded and original value, BUT A1 is coded value. How is it possible a non-coded value has the same value of a coded value ? $\endgroup$ – Questioner Aug 29 at 15:08
  • 1
    $\begingroup$ You could do it with digits. For example, if $X_1 = 4$ and $X_2 = 7$, then $A_1 = 4$, $A_2 = 7$, $A_3 = 4 + 7 \equiv 1 \pmod{10}$, $A_4 = 4 + 2\cdot 7 \equiv 8 \pmod{10}$. Then you can recover $X_1$ from $A_4$ and $A_2$ by $X_1 = A_4 - 2 A_2 = 8 - 2\cdot 7 \equiv 4 \pmod{10}$ as expected. (But $\mathbb Z/10\mathbb Z$, i.e. digits base 10, is not really nice because 10 is composite, not prime, so it doesn't form a field. You're reading up on introductory abstract algebra to learn about these terms, right?) $\endgroup$ – Squeamish Ossifrage Aug 29 at 15:22
  • 2
    $\begingroup$ If that article wasn't clear, and if you're not sure what a field is, consider an introduction to finite fields like Robert J. McEliece's book Finite Fields for Computer Scientists and Engineers, and maybe find another exposition Reed–Solomon coding of which there are many out there. Usually RS is done over binary fields, but the story is a little different from how this article makes it look because binary fields have no notion of ‘2’ as in $A_4 = X_1 + 2 X_2$. You really need grounding in abstract algebra and finite fields like I've been recommending in order to grok it. $\endgroup$ – Squeamish Ossifrage Aug 30 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.