Random linear coding approach to distributed data storage

• US 8,375,102 B2
• Filed: 10/06/2011
• Issued: 02/12/2013
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Koetter, Ralf, Medard, Muriel, Deb, Supratim
• Primary Examiner(s): Baturay, Alicia
• Application Number:
  US13/267,764
• Publication Number:
  US 20120096124A1
• Time in Patent Office: 495 Days
• Field of Search: 709/217
• US Class Current: 709/217
• 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 peer-to-peer network, the method comprising:

receiving, at a peer, a request for at least one code-vector associated with coded pieces of a file, the at least one code-vector and the coded pieces of the file currently stored at the peer, wherein the coded pieces of the file comprise a subset of the file, wherein the 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 in accordance with the formula;

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

3. The method of claim 1, wherein receiving the request for the coded pieces of the file comprises:

receiving the request sent due to the source of the request collectively viewing the transmitted code-vector and at least one code-vector received from at least one respective additional peer as a matrix having a dimension that is equal to a predefined number.

4. The method of claim 3, wherein collectively viewing the transmitted code-vector and the at least one code-vector received from the at least one respective additional peer as the matrix comprises viewing a kr x m matrix of F_q wherein k is the number of pieces stored at the peer, r is the number of peers, and F_q is a matrix having vectors of size s in a field of size q.

5. The method of claim 3, wherein collectively viewing the transmitted code-vector and the at least one code-vector received from the at least one respective additional peer comprises viewing the transmitted code-vector and the at least one code-vector received from the at least one respective additional peer as a matrix having a dimension that is equal to a number of pieces the file is broken into.

6. A non-transitory computer readable medium having computer readable code thereon for providing a random linear coding approach to distributed data storage, the medium comprising:

instructions for receiving, at a peer, a request for at least one code-vector associated with coded pieces of a file, the at least one code-vector and the coded pieces of the file currently stored at the peer, wherein the coded pieces of the file comprise a subset of the file, wherein the coded pieces of the file were randomly determined for storage at the peer by taking a random linear combination of all the pieces of the file in accordance with the formula;

7. The non-transitory computer readable medium of claim 6, wherein the code-vector is calculated in accordance with the formula:

8. The non-transitory computer readable medium of claim 6, wherein the instructions for receiving the request for the coded pieces of the file comprise:

instructions for receiving the request sent due to the source of the request collectively viewing the transmitted code-vector and at least one code-vector received from at least one respective additional peer as a matrix having a dimension that is equal to a predefined number.

9. The non-transitory computer readable medium of claim 8, wherein the instructions for collectively viewing the transmitted code-vector and the at least one code-vector received from the at least one respective additional peer as the matrix comprises instructions for viewing a kr x m matrix of F_q wherein k is the number of pieces stored at the peer, r is the number of peers, and F_q is a matrix having vectors of size s in a field of size q.

10. The non-transitory computer readable medium of claim 8, wherein the instructions for collectively viewing the transmitted code-vector and the at least one code-vector received from the at least one respective additional peer as a matrix comprise viewing the transmitted code-vector and the at least one code-vector received from the at least one respective additional peer as a matrix having a dimension that is equal to a number of pieces the file is broken into.

11. A non-transitory computer readable device having computer readable code thereon for retrieving a file previously stored using a random linear coding approach to distributed data storage, the device comprising:

instructions for receiving, at a peer, a request for at least one code-vector associated with coded pieces of a file, the at least one code-vector and the coded pieces of the file currently stored at the peer, wherein the coded pieces of the file comprises a subset of the file, wherein the coded pieces of the file were randomly determined for storage at the peer by taking a random linear combination of all the pieces of the file in accordance with the formula;