One-sub-symbol linear repair schemes

A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for repairing a single erasure in a Reed-Solomon (RS) code over a finite field F2mr with an evaluation set V={u0=0, . . . , un−1} that is a subspace of size n=2d, for d<mr and divisible by m, wherein a normalized repair bandwidth b≈(n−1)/m and a number of information symbols is k<=2d−2d−dim, in a system of a plurality of n storage nodes and a controller, wherein a content ci of each storage node i is an element of the finite field F2mr and each node stores a vector v whose entries are inverses of non-zero elements of the evaluation set V, the method comprising the steps of

• identifying, by the controller, a failed storage node;
• transmitting, by the controller, an index j0 of the failed storage node to each surviving storage node;
• multiplying, by each surviving storage node i, the content c of each said node i by a j-th component of vector w(i) wherein
• j
• =
• j
• 
• (
• i
• ,
• j
• 0
• )
• =
• {
• j
• 0
• if
• 
• 
• j
• 0
• <
• i
• j
• 0
• -
• 1
• if
• 
• 
• j
• 0
• >
• i
• ,
• wherein w(i)j(i,j0):=vj′ for all i ∈ {0, . . . , j0−1, j0+1, . . . , n} is a permutation of elements of vector v that correspond to the surviving storage nodes, wherein j′ is a unique index in {1, . . . , n−1} such that uj=uj0+ui;
• determining a trace map of a result outi of said multiplication and converting, by each surviving storage node, the result from an m×r bit representation into a reduced representation i of r bits;
• reconstructing, by the controller, content of the failed storage node from the reduced representation of each surviving node's content;
• and
• outputting the reconstructed content of the failed storage node.