Thank you very much.
So yeah, let's start.
I will talk about a bit of the mathematics or the fundamental mathematics of Eurasia coding.
First of all, it's me.
I'm not a software developer.
I'm just a mathematics student.
Currently studying in Oslo.
I'm a big fan of Austin, so that's why I'm here.
Yeah, first, what is Eurasia coding?
So you've probably heard that Eurasia coding is a redundancy technique for storage systems,
so essentially for data protection.
And it enables especially storage efficiency by distributing data in a smart way over different nodes in a cluster.
So what's essentially first done is that we're going to some data and then we split it into k chunks.
And then they are mystically encoded into n chunks.
And by this then n minus k chunks of the encoded chunks are going to be enough to recover all the data.
Yeah, also what's quite important is that it considers transient and prominent failures.
So it's not trying to repair errors in the disks, but just considers them as Eurasia.
Yeah, it has less redundancy than replication.
So that's the nice thing about Eurasia coding.
And it's for example typically used in cloud storage.
So yeah, first bit about the history, so the fundamental idea behind Eurasia coding is presented by was presented by Reed and Solomon in the paper from 1960 polynomial codes of a certain finite fields, which is a very mathematical title.
But it wasn't really applied at that time.
So first the world, the redundant area of independent or inexpensive disks.
And it's usually now applied since the early 2000s.
So now we start with the Reed Solomon code, which is like the fundamental basis of Eurasia coding.
And we consider the simple string head of out and we divided it into five chunks.
Like this, so that they all have the same size.
And then they are encoded, as I said before, and then we get, for example, now eight chunks.
And the important thing is that five of these eight encoded chunks will be enough to recover the whole string head of the data.
But of course, what is this encoding and how do we recover the data?
Therefore, we now need polynomials, which you hopefully have seen at some point in school.
And yeah, we call these numbers a zero to a k minus one coefficients.
And polynomial, for example, looks like this.
So the wet one in the middle, for example, the simple polynomial, a one zero, and the others, is one and the others are all zero.
And above there's one where eight one is two, and a zero is minus one, and then the others are zero.
And the one underneath then has eight two equal to zero point five, and it's then a quadratic polynomial.
Now we need to use a fundamental theorem from mathematics about polynomials.
And therefore, we now try to draw polynomials through points.
So first we look at this point eight, which is simply the point two two with x and y coordinates two and two.
And if we look at very simple polynomials that look like this above, we see, okay, the only one that directly goes through that point is one that's just simply constantly two.
But if we look at polynomials that are a bit more complex, we see that we have different options to draw them through these points.
And if we add another point, we see, okay, there's again only one unique polynomial that directly goes through these two points that looks like this.
But if we again continue the whole thing and consider polynomials of a higher degree, so that a bit more complex, we again get the same that if we would add another point.
There would only be one unique polynomial of that form that would go through the three points.
So this is essentially what we observed, summed up.
And this gives then the theorem.
And this looks a bit overwhelming maybe, but it's just what we observed.
So given K coordinates where the x coordinates should be power assistant, the x is a unique polynomial that looks like this.
With that attains just these points on the graph.
And equivalently, we could also say if we consider distinct points x zero through x k minus one, each polynomial that goes up to k degree k minus one is uniquely determined by its values.
Yeah, how does it help us? And what does the polynomial really do?
The central idea is now to construct the polynomial, almost specifically the coefficients of the polynomial by the data that we split it up.
So we considered these five chunks.
And now if we look at the first chunks, which is just the letters h and e, we have that decimal number for this.
These two letters by just some simple encoding, it does really matter now.
In the example is 26,725.
Then we take this m0 to be the first coefficient in the polynomial.
And that is then done for all the other chunks as well.
But then we have some x values that we multiply them with.
So we get this polynomial, which looks very scary.
And if we try to plot it, it looks also a bit horrible because it attains really, really high values.
But now, why did we have the mathematical result?
Well, we saw from the mathematical result that we can uniquely determine this polynomial by considering the total five points.
So here's again the theorem.
And for example, what is typically done is that we consider the x values zero and up to k minus one.
And these are then, in our example, exactly these points that can be simply computed.
And here they are plotted.
But that now doesn't really introduce redundancy because we know we need these five points to uniquely determine this.
So we consider more points, for example, eight points.
And this would be then the coordinates.
And then the idea is to just distribute these end coordinates that we have now so far on to our cluster.
So they're all saved on different nodes.
And this from these nodes, we can we now have that if we consider any five points, so any five coordinates for polynomial.
We get a uniquely solvable systems of linear equations.
And that's why we can uniquely redetermined our polynomial, which was essentially that data.
So, for example, because we then know it's one, five, and seven fail.
Then from the node zero, we get that the polynomial where you should look like this.
And then from the y-well, you get this also from the node.
And same can be done for all the other nodes that are still left.
And well, this is a system of linear equations in five variables.
And we have five equations, so we can uniquely recover these coefficients, which, again, simply the data we have.
But now, of course, we saw that, for example, for 0.4, we get very, very big values.
So, and if we simply consider the letters, we had two letters, make up 16 bits, but this number would, for example, take 24 bits.
So, we need more space, so it doesn't really make it better.
But that's why then the so-called calor fields are used.
So, this is what is done there.
And that's what also forms these, especially these red-solum and codes.
And what is done there is that we essentially don't look at all the numbers.
But we restrict to using only the integers 0 up to, for example, in our case 2 to the power of 16 minus 1.
And then we don't only have the coefficients in that range, but also the values of the function.
So, p4 would then also be some random sum number in that range.
And of course, the normal computation doesn't work with this.
So, on calor fields, so fields and mathematics also define the specific multiply, multiplication and a specific addition.
So, they have a different system to use this.
But it essentially also only involves more modular calculations and some more divisions.
So, it creates a bit more complexity when calculating, but it's essentially works.
And then, the nice thing about these calor fields is that also this theorem that we had about the uniqueness to recover the coefficients from the polynomial.
Also still holds over these fields and that's why it then works for the with the calor fields.
And then, of course, we have that the numbers that we want to save on the nodes are only of 16 bits and not larger.
So, then with these calor fields, we finally add that we can tolerate n minus k in old failures, but also let is storage optimal,
meaning that we can construct the data from any k of the n chunks with the minimum storage capacity, which is then simply n divided by k.
And, for instance, very, very large clusters like for example, storage systems like Google Colossus as a redundancy value of 1.6,
or Facebook as for the redundancy value of 1.4.
And here, the splitting, for example, explains that Google Colossus also has for splits the data first into 6 chunks and then encodes in total of 9 chunks.
And also very nice thing about these real tournament codes is that the values and k that we looked at, they can be chosen arbitrarily essentially.
We just have this one condition that the number of encoded chunks has to be smaller than 2 to the power of the number of bits from a particular chunk, because otherwise we can solve the system of linear equations.
Another very useful thing is that we can, so if we want to consider scalable storage, so first if we we call the collection of these n and code chunks that we have just a stripe, it's a normal terminology, and then we consider each chunk that we had before as the collection of more chunks.
So for example, here we say that the first chunk is made out of four chunks and the same also holds for the other chunks.
And then we consider to create this polynomial, only for example, for the first line of the data that is given by these division of the chunks.
And then we also get like the first line is then the encoded first line in the uncoded chunks.
And that makes it especially useful when updating or changing the data or also when we covering to make it.
So the computations are smaller because if we have very big chunks that also the computations get much higher.
And another useful thing is that we can configure the retone of the codes also in the systematic form, which says that the final n and coded chunks.
Made off of the k original chunks, so we just have the original with the original data together with the n minus k parity chunks.
So it means that it's also feasible to just read the data and not only consider it in the encoded state.
And yeah, there are also still many more other erasure codes that also just go more into the details of the overhead that is created in repair is an update.
So for instance, regenerating codes, local reconstruction codes is decodes also read and sort of on the density parity codes, but they also all face essentially on this same idea, but with adaptations to make it.
So yeah, that's already it. Thank you very much for your attention. Just feel free to contact me wherever you may or yeah, please ask if you have any questions.
I mean the performance.
Yeah, so the question was about the performance and not so much about the real liability.
I haven't looked at it too closely, but it's essentially depends on the selection of chunks you choose.
And then if for example, if the chunk gets smaller, the computation over to each chunk also gets smaller.
So what's essentially done is when you encode you just calculate values of the of the polynomials, but when you're decoding you're solving a system of linear integration, so and that's very standard mathematical algorithm for us.
So I don't have too much of the details, but yeah, so it's many additions and multiplications essentially.
So I just wanted to mention this set up this very similar to a super chair and some culture here to see the chair, which also leads to the school.
If you have like the secret that you want to share with the parties, so that the parties can recover it.
But the purpose of using essentially the same idea.
I've been calling years ago where I've been calling for two times when you're in coverage.
But I've been seeing that you can recover it.
She's in that right.
It's definitely going on because it's solving the earlier system.
And I think that is a good factor.
It's depending on the details I guess.
That's not a way to do it.
Yeah, so essentially it was noted that it's very similar also to the secret sharing.
And that also for the polynomial interpolation parts, what we saw with the points on the graph.
That instead also.
Another basis could be used.
So for example, like gosh, we have polynomials.
They are known to you.
So yeah, of course, that's all making the performance better.
And you can encode this in very different ways.
But it was just to show what essentially really happens in the usual coding part.
Because it might not have been known to many people.
Then it uses polynomial interpolation.
Yeah.
Questioner, you have to cave for five.
And was what was too much.
And now when I have only a word that is, what was known then I only have to cave.
How do I get to, up to five.
I mean.
So the question was about choosing the end on the cave values for the, when you, for example,
looking only at four bytes.
Well, for four bytes, this eraser coding is essentially not really great.
So it was just a small example.
But typically the chunks are a bit larger.
And the cave can always be shown to be any value.
So it can be anything between one and maybe the number of bits that you have.
So it's really up to choice.
So in modern story, we've got what ourselves compression encryption.
Check sound link.
And where do we could arrange your coding between these layers?
Or what are the triangles?
Thank you for that.
So the question was about where erasure coding is placed in comparison to encrypting.
And different stories.
So I mean the erasure coding part is mainly about the recovering of data and being able to recover.
So I mean if you have encrypted data, I guess you could just consider the encrypted data in the beginning
and then use the encoding by the erasure coding to apply it.
So I think it's two different approaches.
So I mean the encoding part is not really about making it decrypting it and
encrypting it but it's more about the storing part and to recover it easily.
So the question was about what we do if we have, if not all of the redundant nodes die essentially.
But yeah.
So for example in our example only one node would have died.
We could have derived instead of five equations seven.
But then the additional two other equations don't really give us additional information
because we just need the five equations to recover the data.
So but yeah when for example we look at recovering algorithms or things like that then questions like this
become more relevant.
Yeah.
As we give us error detection if we have to do all the specified metrics.
So I'm the additional ones if they don't die out.
Have you error detection data?
Yeah I think so but I mean essentially the erasure codes.
The question was about error detection if we have like additional equations and then see okay the equations don't
line up.
Then so erasure coding was essentially so these read Solomon code to also construct it for more come
off from the telecommunications field and there they also function as error correcting codes.
So yes essentially this could be done but it doesn't have to so yeah it could be used.
Yeah.
Yes.
I'm going to put like correct but from my understanding right now the wide values of the first K chance
carry the semantics of the characters we want to go.
But when it's right how do I choose the next chance to go to the end chance and when some of the first K die
but I have the luck from this end I can reconstruct the polynomial.
Of course I can calculate the coefficient.
But then it would also be as meta data the weeks where use of the first K that each child
to be able to get the information I want.
So the question was about the x and y values that we save in the chunks so I don't know if I understood correctly
but I mean we don't really so we just save the n and coded chunks so in total.
And do the y values carry the semantics of the characters we want to do is the y values and it's only for the n.
Not really so if we for example look at the first coordinate just some coordinate this is the function value and this is determined as we saw here.
By summing over the encodings of the coefficients multiplied with the x values so it all plays together into each chunk.
So the question was about how much space the encoding by Eurasia coding takes and this is really depending on the choice of the values and end K.
So we saw for example here the minimum storage redundancy would be is and divided by K and that is attained.
So if we have if we choose and to be equal to 1 equal to K then of course it doesn't give us anything new but we have the same space.
And depends on these numbers so if for example n is twice the amount of K then it takes twice the space but it still gives us a better reliability on the system except if we are considering just the K value equal to 1.
Yes?
I know it's not your question actually.
And it's not the both methods of all of these things out.
Is there or when you have to wear it?
It's not exactly this one.
And the math for when you like to give it a G.
So the question was about if this is Eurasia coding is also in some hardware.
I think it is used but it's not really hardware specific because it's just about saving these values on hardware.
So I don't know too much about this.
But I think we sure most modern SSDs is some things that we can do.
So like as you can see for the XE3 check list.
Which also I think give you some sort of data correction on your region in the direction.
And we have to have the instruction sets for that.
Yes.
Then you are going to see that this one.
You see, you have to make the same.
Like, you see, do you run the edge?
I don't think I can run.
Yeah, it's on your own code.
It's like version.
Yeah, sure.
Yes?
Okay.
For example, I have a zip code.
Oh, guys.
It's a systemic code.
Can you give any examples that does?
I haven't really looked.
Yeah, the question was about any examples of this.
Where it's not encoded in the systematic form.
I haven't really looked at many other examples but it's essentially all the same thing.
Because you're just changing like the if you consider the matrix that's created by the linear system of equations.
It's just, yeah, applying simple changes.
And then it's equivalent.
But I don't know if it's used in that way, somewhere.
Yeah.
I just have one more.
It'll come in and drop me out.
When you lose this in a large storage area, and you want to restore it.
And you have a redundancy of basically three.
Can you pick any of the other, or any, you can pick any of three of other disks to place the information that this has to be restored.
So, the main advantage that just struck me on the other side.
So, when the advantage would be that I don't have to read the copies from just one disk on it.
You set your eyes again.
I can just read one first of data from one disk, one third of the data from another disk.
And have it.
Because I have enough redundancy of three other disks.
Yeah.
Just want to make that come in there.
Yeah.
If you have to.
Thank you.
Okay.
Thank you.
Any more questions?
Comments we can have later in the hallway, sir.
All right.
Thank you.