Random linear coding approach to distributed data storage
First Claim
1. A computer-implemented method in which a computer system performs operations using random linear coding for performing distributed data storage in a peer-to-peer network, the method comprising:
- breaking a file into a plurality of pieces;
determining a number of coded-pieces each peer can store;
determining the coded-pieces for each peer by taking random linear combination of pieces of the file;
calculating an associated code vector for said random combination of pieces; and
storing a respective random combination of coded pieces and the associated code vector at each peer of said number of peers, wherein determining a random combination of particular pieces of said plurality of pieces to store at a peer is done in accordance with the formula;
2 Assignments
0 Petitions
Accused Products
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.
30 Citations
16 Claims
-
1. A computer-implemented method in which a computer system performs operations using random linear coding for performing distributed data storage in a peer-to-peer network, the method comprising:
-
breaking a file into a plurality of pieces; determining a number of coded-pieces each peer can store; determining the coded-pieces for each peer by taking random linear combination of pieces of the file; calculating an associated code vector for said random combination of pieces; and storing a respective random combination of coded pieces and the associated code vector at each peer of said number of peers, wherein determining a random combination of particular pieces of said plurality of pieces to store at a peer is done in accordance with the formula; - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer-implemented method in which a computer system performs operations for retrieving a file comprising:
-
collecting code vectors from at least one peer; viewing collected code vectors as a matrix, wherein said viewing collected code vectors as a matrix comprises viewing said collected code vectors as a kr x m matrix of Fq wherein k is the number of pieces stored at a peer, r is the number of peers and Fq is a matrix having vectors of size s in a field of size q; determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and when the dimension of the matrix equals the predefined number, then recovering said file using the collection of code vectors in the matrix. - View Dependent Claims (8)
-
-
9. A non-transitory computer readable storage medium having computer readable code thereon for providing a random linear coding approach to distributed data storage, the medium including instructions in which a computer system performs operations comprising:
-
instructions for breaking a file into a plurality of pieces; instructions for determining a number of peers to use to store pieces of the file; instructions for determining a random combination of particular pieces of said plurality of pieces to store at a peer of the number of peers in the network; instructions for calculating an associated code vector for said random combination of particular pieces; and instructions for storing a respective random combination of pieces and the associated code vector at each peer of said number of peers wherein said determining a random combination of particular pieces of said plurality of pieces to store at a peer is done in accordance with the formula; - View Dependent Claims (10, 11, 12, 13, 14)
-
-
15. A non-transitory computer readable storage medium having computer readable code thereon for retrieving a file previously stored using a random linear coding approach to distributed data storage, the medium including instructions in which a computer system performs operations comprising:
-
instructions for collecting code vectors from at least one peer; instructions for viewing collected code vectors as a matrix, wherein said viewing collected code vectors as a matrix comprises viewing said collected code vectors as a kr x m matrix of Fq wherein k is the number of pieces stored at a peer, r is the number of peers and Fq is a matrix having vectors of size s in a field of size q; instructions for determining whether a dimension of the matrix is equal to a predefined number, and instructions for when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and instructions for when the dimension of the matrix equals the predefined number, then recovering said file using the collection of code vectors in the matrix. - View Dependent Claims (16)
-
Specification