Random linear coding approach to distributed data storage

• US 9,165,013 B2
• Filed: 11/16/2012
• Issued: 10/20/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
• Primary Examiner(s): Baturay, Alicia
• Application Number:
  US13/678,982
• Publication Number:
  US 20130073697A1
• Time in Patent Office: 1,068 Days
• Field of Search: 709/217
• 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 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;

2. The method of claim 1 wherein the code-vector is calculated in accordance with the formula:

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;

4. The non-transitory computer readable medium of claim 3 further comprising instructions wherein the code-vector is calculated in accordance with the formula:

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;

6. The computer system of claim 5 wherein the code-vector is calculated in accordance with the formula: