Generation and verification of erasure encoded fragments

A computer-readable storage medium having computer-executable instructions stored thereupon to generate a specified erasure encoded fragment from a plurality of erasure encoded fragments without reconstructing a data file, the plurality of erasure encoded fragments being related to an erasure coding scheme and the data file, the instructions, when executed by a computer, cause the computer to:

• determine, at a first server of a plurality of servers, the specified erasure encoded fragment to be generated;
• determine erasure encoded fragments of the plurality of erasure encoded fragments that are available and valid;
• select erasure encoded fragments of the plurality of available and valid erasure encoded fragments that are to be used to generate the specified erasure encoded fragment;
• generate a composite matrix based upon the erasure encoding scheme, the erasure encoded fragments, and the specified erasure encoded fragment;
• generate partial sums by multiplying the composite matrix and the erasure encoded fragments;
• and
• generate, at the first server or a second server of the plurality of servers that is different from the first server, the specified erasure encoded fragment by at least one of (1) receiving and summing the partial sums at the first server or the second server or (2) receiving the partial sums and summing the partial sums with a partial sum generated by the first server or the second server.

A system to generate a specified erasure encoded fragment from a plurality of erasure encoded fragments without reconstructing a data file, the plurality of erasure encoded fragments being related to an erasure coding scheme and the data file, the system comprising:

• a first server, of a defined set of servers, to:
• either identify or receive a first identification of the specified erasure encoded fragment to be generated;
• either identify or receive a second identification of erasure encoded fragments selected to be used to generate the specified erasure encoded fragment;
• generate a composite matrix based upon the erasure encoding scheme, the erasure encoded fragments, and the specified erasure encoded fragment;
• generate the specified erasure encoded fragment based upon the composite matrix and the erasure encoded fragments;
• wherein one or more servers in the defined set of servers are to:
• at least one of (1) receive the composite matrix and the second identification of the erasure encoded fragments in a corresponding set of erasure encoded fragments for the one or more servers, or (2) receive the first identification of the specified erasure encoded fragment and the second identification of the erasure encoded fragments in the corresponding set of erasure encoded fragments for the one or more servers, and generate the composite matrix based upon the erasure encoding scheme, the erasure encoded fragments, and the specified fragment;
• retrieve the erasure encoded fragments identified in the corresponding set of erasure encoded fragments for the one or more servers,
• generate a partial sum based upon the composite matrix and the erasure encoded fragments retrieved for the one or more servers,
• send the partial sum to a generating server of the defined set of servers;
• and
• wherein the generating server is either (1) the first server or (2) a second server in the defined set of servers that is different from the first server, and wherein the generating server is to:
• receive the partial sums from the one or more servers, and at least one of (1) sum the partial sums to generate the specified erasure encoded fragment or (2) sum the partial sums with a partial sum generated by the generating server to generate the specified erasure encoded fragment.

A computer-implemented method to generate a specified erasure encoded fragment from a plurality of erasure encoded fragments without reconstructing a data file, the plurality of erasure encoded fragments being related to an erasure encoding scheme and the data file, the method comprising:

• receiving, at one or more servers of a plurality of servers, at least one of (1) a first identification of a first erasure encoded fragment to be used to generate the specified erasure encoded fragment, the first identification corresponding to a second erasure encoded fragment at the one or more servers or (2) a second identification of the specified erasure encoded fragment;
• generating a composite matrix based upon the erasure encoding scheme, the second erasure encoded fragment, and the specified erasure encoded fragment;
• receiving the composite matrix or information identifying the composite matrix at a first server of the plurality of servers;
• multiplying the composite matrix by the second erasure encoded fragment to generate a first partial sum;
• and
• sending the first partial sum to a generating server that at least one of (1) sums the first partial sum with a second partial sum received at the generating server to generate the specified erasure encoded fragment or (2) sums the first partial sum with a third partial sum generated by the generating server to generate the specified erasure encoded fragment.

A system for generating a specified erasure encoded fragment related to a data file without reconstructing the data file, the system comprising:

• a first server of a plurality of servers that:
• at least one of generates a first identification of the specified erasure encoded fragment to be generated, or receives the first identification;
• determines a second identification of one or more erasure encoded fragments available from one or more other servers of the plurality of servers;
• based at least partly on the second identification, selects a set of erasure encoded fragment from the one or more erasure encoded fragments, creating a selected erasure encoded fragment set distributed among the one or more other servers, the selected erasure encoded fragment set not including the specified erasure encoded fragment;
• and
• at least one of (1) generates a composite matrix based at least partly on the erasure encoding scheme, the selected erasure encoded fragment set, and the specified erasure encoded fragment, and sends, to the one or more other servers, the composite matrix, or (2) sends, to the one or more other servers, the first identification and a third identification of the selected erasure encoded fragment set;
• wherein the one or more other servers:
• at least one of (1) receives the composite matrix, or (2) receives the first identification and the third identification, and generates the composite matrix based at least partly on the erasure encoding scheme, the selected erasure encoded fragment set, and the specified erasure encoded fragment;
• generates one or more partial sums based at least partly on the composite matrix and the selected erasure encoded fragment set;
• and
• sends the one or more partial sums to a generating server of the plurality of servers;
• wherein the generating server:
• receives the one or more partial sums, and at least one of (1) sums the one or more partial sums to generate the specified erasure encoded fragment or (2) sums the one or more partial sums to generate an intermediate partial sum, and sums the intermediate partial sum with a second partial sum generated by the generating server to generate the specified erasure encoded fragment.