Simple Entanglement Codes
Simple Entanglement Codes
Practical Codes for Storage Systems
Practical Codes for Storage Systems
An Introduction to Entanglement Codes
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 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:
In[]:=
g=Graph[{01,12,23,34,45,56},VertexLabels"Name",VertexSizeMedium,VertexStyle{0Red,6Red}]
Out[]=
Write Data
Write Data
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:
In[]:=
vertex=AssociationThread[VertexList[g],vertexValues]
Out[]=
00,172,2101,3108,4108,5111,60
We can visualize the entanglement chain using the vertex weight to store plain data and the edge weight to store encoded data:
In[]:=
g=Graph[{01,12,23,34,45,56},VertexSizeMedium,VertexStyle{0Red,6Red},VertexWeightvertexValues,EdgeWeightencodedData,VertexLabels"VertexWeight",EdgeLabels"EdgeWeight"]
Out[]=
Read Data
Read Data
Data can be recovered using nodes or edges.
Method 1: read plain text from vertices (without decoding):
In[]:=
Row[FromCharacterCode[PropertyValue[{g,#},VertexWeight]]&/@{1,2,3,4,5}]
Out[]=
Hello
In[]:=
FromCharacterCode[BitXor@@@Partition[encodedData,2,1]]
Out[]=
Hello
Decoding in Detail
Decoding in Detail
We can read the contents of a node by applying the bitwise XOR to the weight of its two adjacent edges.
For example, to read “e” (character code 101), we use the adjacent edges, which contain 72 and 45:
In[]:=
FromCharacterCode[BitXor[encodedData[[2]],encodedData[[3]]]]
Out[]=
e
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)
Failure Patterns (/ + 4)
AUTHORSHIP INFORMATION
Vero Estrada-Galinanes
Date of creation
Author email address (please use the email associated with your Wolfram User ID)