Random Linear Coding Approach To Distributed Data Storage

• US 20150304419A1
• Filed: 07/01/2015
• Published: 10/22/2015
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Medard, Muriel, Deb, Supratim, Koetter, Ralf
• Granted Patent: US 9,680,928 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

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.

Claims

1. A method of using random linear coding for performing distributed data storage in a network, the method comprising:

receiving, at a downloader in a network with r peers, a combination of m stored pieces, wherein m is the number of file pieces a file is broken into;

information to recover said m file pieces from m stored pieces; and

wherein a peer has no knowledge about what other peers have stored, and therefore said peers do not coordinate for storing pieces of a file.

2. The method of claim 1 wherein said m file pieces of said file are viewed as elements in F_q^s which are vectors of size s in a field of size q.

3. The method of claim 2 wherein chunks of said file are denoted as c_i, i=1, 2, . . . m, and each peer stores k random combinations of c_i'"'"'s.

4. The method of claim 3 further comprising storing an associated code vector (β

₁, β

₂, . . . , β

_m) for each of said k pieces.

5. The method of claim 4 wherein the elements with a particular peer are f₁, f₂, . . . f_k.

6. The method of claim 5 wherein an element of a peer f_i can be represented as

7. The method of claim 6 wherein there are a total of kr m-dimensional code-vectors available for said downloader, wherein each of said code-vectors represents a random mixture of said file pieces, wherein a collection of said vectors can be viewed as a kr×

m matrix over F_q and wherein the complete file can be recovered once the rank of said matrix is m.

8. 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 downloader in a network with r peers, a combination of m stored pieces, wherein m is the number of file pieces a file is broken into;

information to recover said m file pieces from m stored pieces; and

wherein a peer has no knowledge about what other peers have stored, and therefore said peers do not coordinate for storing pieces of a file.

9. The computer readable medium of claim 8 wherein said m file pieces of said file are viewed as elements in F_q^s which are vectors of size s in a field of size q.

10. The computer readable medium of 9 wherein chunks of said file are denoted as c_i, i=1, 2, . . . m, and each peer stores k random combinations of c_i'"'"'s.

11. The computer readable medium of claim 10 further comprising storing an associated code vector (β

₁, β

₂, . . . , β

_m) for each of said k pieces.

12. The computer readable medium of claim 11 wherein the elements with a particular peer are f₁, f₂, . . . f_k.

13. The computer readable medium of claim 12 wherein an element of a peer f_i can be represented as

14. The computer readable medium of claim 13 wherein there are a total of kr m-dimensional code-vectors available for said downloader, wherein each of said code-vectors represents a random mixture of said file pieces, wherein a collection of said vectors can be viewed as a kr×

m matrix over F_q and wherein the complete file can be recovered once the rank of said matrix is m.

15. A downloader 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 a downloader in a network with r peers, a combination of m stored pieces, wherein m is the number of file pieces a file is broken into;

information to recover said m file pieces from m stored pieces; and

wherein a peer has no knowledge about what other peers have stored, and therefore said peers do not coordinate for storing pieces of a file.

16. The downloader of claim 15 wherein said m file pieces of said file are viewed as elements in F_q^s which are vectors of size s in a field of size q.

17. The downloader of claim 16 wherein chunks of said file are denoted as c_i, i=1, 2, . . . m, and each peer stores k random combinations of c_i'"'"'s.

18. The downloader of claim 17 further comprising storing an associated code vector (β

₁, β

₂, . . . , β

_m) for each of said k pieces.

19. The downloader of claim 18 wherein the elements with a particular peer are f₁, f₂, . . . f_k.

20. The downloader of claim 19 wherein an element of a peer f_i can be represented as

21. The downloader of claim 20 wherein there are a total of kr m-dimensional code-vectors available for said downloader, wherein each of said code-vectors represents a random mixture of said file pieces, wherein a collection of said vectors can be viewed as a kr×

m matrix over F_q and wherein the complete file can be recovered once the rank of said matrix is m.