Erasure coding technique for scalable and fault tolerant storage system
First Claim
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.
4 Assignments
0 Petitions
Accused Products
Abstract
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 including 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, 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, and wherein a set of n different components selected from the original components and new components contains more redundant information about the block than the set of n original components.
33 Citations
17 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
Specification