×

Erasure coding technique for scalable and fault tolerant storage system

  • US 7,979,771 B2
  • Filed: 04/04/2007
  • Issued: 07/12/2011
  • Est. Priority Date: 04/04/2006
  • Status: Active Grant
First Claim
Patent Images

1. A method for encoding a block of data to allow it to be stored or transmitted correctly in the face of accidental or deliberate modifications, the method comprising:

  • constructing a number n greater than one of original components, each of which is derived from the block and each of which is smaller than the block; and

    combining original components to construct a number m greater than one of new components, the combining comprising;

    scaling original components to determine scaled original components; and

    accumulating scaled original components to determine new components;

    wherein each of the new components is smaller than the sum of the sizes of the original components combined to produce it;

    wherein the block can be reconstructed from any set of n different components selected from the original components and new components;

    wherein the size of a one of the new components is larger than the size of a one of the original components that were combined to construct it;

    wherein the scaling step includes an operation in which a first original component is used to determine a first operand to a multiplication operation of a non-finite commutative ring with identity; and

    wherein the accumulating step includes an operation in which a first scaled original component is used to determine a first operand to an addition operation of the non-finite commutative ring with identity.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×