Random linear coding approach to distributed data storage
A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.
1. A method of using random linear coding for performing distributed data storage in a network, the method comprising:
receiving, at a peer, coded pieces of a file, wherein said coded pieces of the file were randomly determined for storage at the peer as a result of taking a random linear combination of all the pieces of the file, wherein said taking a random linear combination of all the pieces of the file is done in accordance with the formula:
f
i
=
∑
j
=
1
m
β
i
c
i
,
wherein f is an element within the peer, m is the number of pieces the file is broken into, β is an element of a finite field of vectors and c is a particular piece of the file;
receiving, at said peer, at least one code-vector associated with the coded pieces of said file; and
storing, at said peer, said coded pieces of a file and said at least one code-vector associated with the coded pieces of said file, wherein said coded pieces of the file comprise a subset of said file.
2. The method of claim 1 wherein the code-vector is calculated in accordance with the formula:
Pr
(
β
i
=
β
)
=
1
q
∀
β
∈
F
q
wherein F is the field of vectors, and q is the field size.
3. A non-transitory computer readable medium having computer readable code thereon for using random linear coding for performing distributed data storage in a network, the medium comprising:
instructions for receiving, at a peer, coded pieces of a file, wherein said coded pieces of the file were randomly determined for storage at the peer as a result of taking a random linear combination of all the pieces of the file, wherein said taking a random linear combination of all the pieces of the file is done in accordance with the formula:
f
i
=
∑
j
=
1
m
β
i
c
i
,
wherein f is an element within the peer, m is the number of pieces the file is broken into, β is an element of a finite field of vectors and c is a particular piece of the file;
instructions for receiving, at said peer, at least one code-vector associated with the coded pieces of said file; and
instructions for storing, at said peer, said coded pieces of a file and said at least one code-vector associated with the coded pieces of said file, wherein said coded pieces of the file comprise a subset of said file.
4. The non-transitory computer readable medium of claim 3 further comprising instructions wherein the code-vector is calculated in accordance with the formula:
Pr
(
β
i
=
β
)
=
1
q
∀
β
∈
F
q
wherein F is the field of vectors, and q is the field size.
5. A computer system comprising:
a memory;
a processor;
a communications interface;
an interconnection mechanism coupling the memory, the processor and the communications interface; and
wherein the memory is encoded with an application providing random linear coding for performing distributed data storage in a network, that when performed on the processor, provides a process for processing information, the process causing the computer system to perform the operations of:
receiving, at said computer system, coded pieces of a file, wherein said coded pieces of the file were randomly determined for storage at the peer as a result of taking a random linear combination of all the pieces of the file, wherein said taking a random linear combination of all the pieces of the file is done in accordance with the formula:
f
i
=
∑
j
=
1
m
β
i
c
i
,
wherein f is an element within the peer, m is the number of pieces the file is broken into, β is an element of a finite field of vectors and c is a particular piece of the file;
receiving, at said computer system, at least one code-vector associated with the coded pieces of said file; and
storing, at said computer system, said coded pieces of a file and said at least one code-vector associated with the coded pieces of said file, wherein said coded pieces of the file comprise a subset of said file.
6. The computer system of claim 5 wherein the code-vector is calculated in accordance with the formula:
Pr
(
β
i
=
β
)
=
1
q
∀
β
∈
F
q
wherein F is the field of vectors, and q is the field size.