Entanglement codes generate redundant information to protect content against failures in a storage system. The method increases the reliability and also improves performance because it creates multiple paths to read data using combinations of elements stored in the system.
Vero Estrada-Galinanes
Simple Entanglement Codes
Simple entanglements create chains of interdependent elements that alternate data represented by a vertex and redundant information represented by an edge.
Here is a visualization of an open entanglement chain. The first and last vertices are virtual elements and do not contain information. The first vertex contains the initial condition of the chain:
Vertices represent data. They can store anything, e.g. a digit, numbers, charys, strings or large chunks of data. The only constraint is that all of them must store the same amount of information.
In this example, the chain will store “Hello”. First, we convert the string to character codes:
In[]:=
vertexValues=ToCharacterCode["Hello"]
Out[]=
{72,101,108,108,111}
The encoder uses the function BitXor to compute the bitwise XOR of the last two elements of the chain. The input consists of the vertex being encoded and its incident edge (whose weight was generated during the encoding of its predecessor vertex and contains redundant information derived from all the predecessor vertices).
If the vertex values are known, the encoding process is equivalent to compute the cumulative bitwise XOR operations of the elements of the vertexValues list:
In[]:=
encodedData=FoldList[BitXor,0,vertexValues]
Out[]=
{0,72,45,65,45,66}
The list of vertexValues only contains the values for vertices 1–5. Let’s fix it.
To fill the virtual vertices with some content, we add zeros at the first and last positions of the list:
In[]:=
vertexValues=Insert[vertexValues,0,{{1},{-1}}]
Out[]=
{0,72,101,108,108,111,0}
Now we can redefine the graph using the new content.
We could describe vertices with associations. The key is the index/label of the vertex, and the value contains one element of the vertexValues list:
We can also recompute the value of an edge. There are two ways to do this, depending on the direction we are moving on the chain. In this example, we recompute
encodedData[[3]]
.
Move from left to right:
In[]:=
BitXor[encodedData[[2]],vertexValues[[3]]]
Out[]=
45
Move from right to left:
In[]:=
BitXor[encodedData[[4]],vertexValues[[4]]]
Out[]=
45
Failure Patterns (/ + 4)
AUTHORSHIP INFORMATION
Vero Estrada-Galinanes
Date of creation
Author email address (please use the email associated with your Wolfram User ID)