Method of constructing flat XOR codes from integer indexed tanner graphs

A non-transient computer readable medium containing program instructions for causing a computer to execute a method comprising:

• improving data recovery upon a disk failure in a system having a predetermined number of data disks in which constructed erasure codes (INT-codes) are flat XOR erasure code by:
• selecting a predetermined acceptable number of failures for the system;
• constructing a first Tanner graph for a two failures acceptable system having the predetermined number of data disks;
• determining a first erasure code from the first Tanner graph;
• and
• repeating the constructing step and the determining step by increasing the predetermined acceptable number of failures by one and (a) constructing another Tanner graph in response to increasing the predetermined acceptable number of failures and an increased number of parity nodes and (b) determining a subsequent erasure code from the another Tanner graph, wherein the constructing another Tanner graph and the determining the subsequent erasure code repeat until an erasure code is determined for the predetermined number of failures for the system, and wherein the erasure code is flat XOR code in which each strip includes only one element of either data or parity, Tanner graphs constructed from the method include an index for each symbol node that represents either a data symbol or a parity symbol, and encoding and decoding of the erasure code are based on integer indices in the Tanner graphs constructed from the method.

A system comprising:

• an apparatus having a predetermined number of data disks;
• and
• a computer for defining a flat XOR erasure code, having a processor configured to improve data recovery when one of the data disks fails by:
• select a predetermined acceptable number of failures for the system;
• construct a first Tanner graph for a two failures acceptable system having the predetermined number of data disks;
• determine a first erasure code from the first Tanner graph;
• and
• repeat the constructing step and the determining step by increasing the predetermined acceptable number of failures by one and (a) constructing another Tanner graph in response to increasing the predetermined acceptable number of failures and an increased number of parity nodes and (b) determining a subsequent erasure code from the another Tanner graph, wherein the constructing another Tanner graph and the determining the subsequent erasure code repeat until an erasure code is determined for the predetermined number of failures for the system, and wherein the erasure code is flat XOR code in which each strip includes only one element of either data or parity, Tanner graphs constructed from the computer include an index for each symbol node that represents either a data symbol or a parity symbol, and encoding and decoding of the erasure code are based on integer indices in the Tanner graphs constructed from the computer.