Scheme for information dispersal and reconstruction

Claim 2

A process for protecting against loss and for enhancing accessibility in storage or memory, or protecting against loss and enhancing speed of transmission on communication paths, of information which is represented in storage or memory, or represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said process comprising transforming and breaking apart said information among a set of smaller assemblages of elements of said finite field or computational structure, and dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, or by storing said assemblages in multiple storage or memory locations, in a manner that is expected to yield no fewer than a required number of said assemblages, said step of transforming and breaking apart comprising representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i :i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {C i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r-th said group of elements, and assembling the n assemblages such that the i-th assemblage comprises the elements {C i ,r : r=1, . . . , N/m}.

Claim 3

A method for reconstructing information from m available assemblages that were generated by the process of claim 1, comprising forming m vectors {α i : i=1, . . . ,m} derived from the m vectors a i that were used to form the elements c i ,r of the available m assemblages, generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of the m available assemblages, and reassembling the information from the thus generated N elements.

Claim 4

A process for protecting against loss and enhancing accessibility in a partitioned or distributed storage or memory system of the kind having portions or components prone to faults or inaccessibilities, of information which is represented in said storage or memory system, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said process comprising transforming and breaking apart said information into smaller assemblages of elements of said finite field or computational structure, and dispersing said information by storing said assemblages in multiple portions or components of said storage or memory system, in a manner that is expected to yield no fewer than a required number, m, of said assemblages, at least some said assemblages being stored in different said portions or components, retrieving at least said required number of said assemblages from said storage or memory system, and reconstructing said information from said retrieved assemblages, said step of transforming and breaking apart comprising representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . ,n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . ,N/m} for assembly into n said assemblages, each element C i ,r being generated as the product of a vector a i times the elements of the r th said group of elements, and assembling the n assemblages such that the i th assemblage comprises the elements {c i ,r, r=1, . . . , N/m); said step of reconstructing said information from said retrieved assemblages comprising: forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to form the elements c.sub. i ,r of the retrieved assemblages, and generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said retrieved assemblages.

Claim 5

A process for protecting against loss and enhancing accessibility in a partitioned or distributed storage or memory system of the kind having portions or components prone to faults or inaccessibilities, of information which is represented in said storage or memory system, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said process comprising transforming and breaking apart said information into smaller assemblages of elements of said finite field or computational structure, and dispersing said information by storing said assemblages in multiple portions or components of said storage or memory system, in a manner that is expected to yield no fewer than a required number, m, of said assemblages, at least some said assemblages being stored in different said portions or components, retrieving at least said required number of said assemblages from said storage or memory system, and reconstructing said information from said retrieved assemblages, said step of transforming and breaking apart comprising representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . ,n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . ,N/m} for assembly into n said assemblages, each element C i ,r being generated as the product of a vector a i times the elements of the r th said group of elements, and assembling the n assemblages such that the i th assemblage comprises the elements {c i ,r, r=1, . . . , N/m); said step of reconstructing said information from said retrieved assemblages comprising: forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to form the elements c.sub. i ,r of the retrieved assemblages, and generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said retrieved assemblages.

Claim 6

A process for protecting against loss and enhancing speed of transmission on communication paths, or information which is represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said communication links being prone to faults or congestions, said process comprising transforming and breaking apart said information into n smaller assemblages of elements of said finite field or computational structure, and dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, in a manner that is expected to yield no fewer than a required number, m, of said assemblages, receiving at least said required number of said assemblages from said paths, and reconstructing said information from said retrieved assemblages, said step of transforming and breaking apart comprising: representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where m N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . ,N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r th said group of elements, and assembling the n assemblages such that the i th assemblage comprises the elements {C i ,r : r=1, . . . , N/m}; said step of reconstructing said information from said received assemblages comprising: forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to form the elements c i ,r of the received assemblages, and, generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said received assemblages.

Claim 7

A process for protecting against loss and enhancing speed of transmission on communication paths, or information which is represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said communication links being prone to faults or congestions, said process comprising transforming and breaking apart said information into n smaller assemblages of elements of said finite field or computational structure, and dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, in a manner that is expected to yield no fewer than a required number, m, of said assemblages, receiving at least said required number of said assemblages from said paths, and reconstructing said information from said retrieved assemblages, said step of transforming and breaking apart comprising: representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where m N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . ,N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r th said group of elements, and assembling the n assemblages such that the i th assemblage comprises the elements {C i ,r : r=1, . . . , N/m}; said step of reconstructing said information from said received assemblages comprising: forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to form the elements c i ,r of the received assemblages, and, generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said received assemblages.

Claim 8

A process for protecting against loss and for enhancing accessibility in storage or memory, and protecting against loss and enhancing speed of transmission in a network, of information which is represented in storage or memory, and represented as data signals on said network, said network and storage or memory being part of a distributed processing system of the kind having nodes associated with storage or memory devices, said nodes being interconnected in said network, and in which said storage or memory devices are prone to faults or inaccessibilities, said process comprising transforming and breaking apart said information into smaller assemblages of elements of said finite field or computational structure, and dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, and by storing said assemblages in multiple said storage or memory devices in said nodes, in a manner that is expected to yield no fewer than a required number, m, of assemblages, retrieving at least said required number of assemblages from said storage or memory devices via said network, and reconstructing said information from said retrieved assemblages, and reassembling the information from the thus generated elements, said step of transforming and breaking apart comprising: representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector α i times the elements of the r th said group of elements, and assembling the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}; said step of reconstructing said information from said retrieved assemblages comprising: forming m vectors {a i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m retrieved assemblages, and generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said retrieved assemblages.

Claim 9

A process for protecting against loss and for enhancing accessibility in storage or memory, and protecting against loss and enhancing speed of transmission in a network, of information which is represented in storage or memory, and represented as data signals on said network, said network and storage or memory being part of a distributed processing system of the kind having nodes associated with storage or memory devices, said nodes being interconnected in said network, and in which said storage or memory devices are prone to faults or inaccessibilities, said process comprising transforming and breaking apart said information into smaller assemblages of elements of said finite field or computational structure, and dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, and by storing said assemblages in multiple said storage or memory devices in said nodes, in a manner that is expected to yield no fewer than a required number, m, of assemblages, retrieving at least said required number of assemblages from said storage or memory devices via said network, and reconstructing said information from said retrieved assemblages, and reassembling the information from the thus generated elements, said step of transforming and breaking apart comprising: representing said information by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector α i times the elements of the r th said group of elements, and assembling the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}; said step of reconstructing said information from said retrieved assemblages comprising: forming m vectors {a i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m retrieved assemblages, and generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said retrieved assemblages.

Claim 12

The method of claim 1, 2, 3, 4, 5 or 6 wherein said elements comprise equal-sized bytes.

Claim 13

The method of claim 7 wherein said elements are members of a field having at least as many elements as the number of possible values of said byte.

Claim 14

The method of claim 8 wherein said field has no more elements than said number of possible values.

Claim 15

The method of claim 8 wherein the field is the field Z p of residues (mod p) where p is a prime number greater than the highest-valued possible said byte.

Claim 16

The method of claim 1, 2, 3, 4, 5, or 6 wherein said information is represented as a string of said elements, and said groups comprise segments of said string, each segment being a sequence of successive said elements.

Claim 17

The method of claim 1, 2, 3, 4, 5, or 6 further comprising generating fingerprints based on said pieces, communicating or storing said fingerprints, and testing said fingerprints for authenticity as the basis for deciding whether to accept any of said pieces for the process of reconstructing the information.

Claim 18

The method of claim 3 wherein a fault or inaccessibility of a given portion or component does not necessarily also entail a fault or inaccessibility of another said portion or component.

Claim 19

The method of claim 4 wherein a fault or congestion of a given link at a given time does not necessarily also entail a fault or congestion of said given link at another time or a fault or congestion of another said link.

Claim 20

The method of claim 5 wherein a fault or inaccessibility of a given storage device does not necessarily also entail a fault or inaccessibility of another said storage device.

Claim 21

The method of claim 6 wherein a failure or congestion of a given path at a given time does not necessarily also entail a failure or congestion of said given path at another time or a failure or congestion of another path.

Claim 22

The method of claim 8 wherein the field is the field GF(2 q ) for q-bit long bytes.

Claim 23

Apparatus for for protecting against loss and for enhancing accessibility in storage or memory, or protecting against loss and enhancing speed of transmission on communication paths, of information which is represented in storage or memory, or represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said apparatus comprising means for transforming and breaking apart said information among a set of smaller assemblages of elements of said finite field or computational structure and a disperser for dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, or by storing said assemblages in multiple storage or memory locations, in a manner that is expected to yield no fewer than a required number of said assemblages, said means for transforming and breaking apart comprising a converter for representing said information by N elements of said field or computational structure, a segmenter for grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, a vector generator for selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for assembling the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}.

Claim 24

Apparatus for for protecting against loss and for enhancing accessibility in storage or memory, or protecting against loss and enhancing speed of transmission on communication paths, of information which is represented in storage or memory, or represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said apparatus comprising means for transforming and breaking apart said information among a set of smaller assemblages of elements of said finite field or computational structure and a disperser for dispersing said information by transmitting said smaller assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, or by storing said assemblages in multiple storage or memory locations, in a manner that is expected to yield no fewer than a required number of said assemblages, said means for transforming and breaking apart comprising a converter for representing said information by N elements of said field or computational structure, a segmenter for grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, a vector generator for selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for assembling the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}.

Claim 25

Apparatus for reconstructing information from an available set of m assemblages that were generated by dispersing the information, by, representing said information packet by N elements of a field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r-th said group of elements, and assembling the n pieces such that the i-th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}, the apparatus comprising a matrix processor for forming an m×m matrix whose rows are the m vectors a i that were used to form the characters c i ,r of the available m assemblages, and for inverting the m×m matrix, a calculator for generating the N characters of the data signal by multiplying the inverted matrix times groups of the elements c i ,r, and an assembler for reassembling the N characters to form the information.

Claim 26

Apparatus for reconstructing information from an available set of m assemblages that were generated by dispersing the information, by, representing said information packet by N elements of a field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r-th said group of elements, and assembling the n pieces such that the i-th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}, the apparatus comprising a matrix processor for forming an m×m matrix whose rows are the m vectors a i that were used to form the characters c i ,r of the available m assemblages, and for inverting the m×m matrix, a calculator for generating the N characters of the data signal by multiplying the inverted matrix times groups of the elements c i ,r, and an assembler for reassembling the N characters to form the information.

Claim 27

The apparatus of claim 18 or 19 wherein said calculator comprises a memory and an associated processor.

Claim 28

The apparatus of claim 20 wherein said memory comprises a high-speed cache memory.

Claim 29

The apparatus of claim 20 wherein said processor comprises an arithmetic unit, a vector processor, a systolic array processor, or a set of any of them in parallel.

Claim 30

Apparatus for protecting against loss and enhancing accessibility in a partitioned or distributed storage or memory system of the kind having portions or components prone to faults or inaccessibilities, of information which is represented in said storage or memory system., said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said apparatus comprising: means for transforming and breaking apart said information into smaller assemblages of elements of said finite field or computational structure, storage or memory for storing said assemblages in said portions or components of said storage or memory system, at least some pieces being stored in different said portions or components, said means for transforming and breaking apart comprising a converter for representing said information by N elements of a field or computational structure, a segmenter for grouping said N elements into N/m groups of m elements, where m is less than N, a vector generator for selecting a set of vectors {a i : i=1, . . . , n} each having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into said n assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for generating the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}; and a reconstructor for retrieving at least m of said assemblages from portions or components of said storage or memory system, and for reconstructing said information from said m retrieved assemblages, said reconstructor comprising a processor for forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m retrieved assemblages, a calculator for generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said m retrieved assemblages, and an assembler for reassembling the information from the thus generated N elements.

Claim 31

Apparatus for protecting against loss and enhancing accessibility in a partitioned or distributed storage or memory system of the kind having portions or components prone to faults or inaccessibilities, of information which is represented in said storage or memory system., said information comprising data elements, each said data element representable as an element of a finite field or computational structure, said apparatus comprising: means for transforming and breaking apart said information into smaller assemblages of elements of said finite field or computational structure, storage or memory for storing said assemblages in said portions or components of said storage or memory system, at least some pieces being stored in different said portions or components, said means for transforming and breaking apart comprising a converter for representing said information by N elements of a field or computational structure, a segmenter for grouping said N elements into N/m groups of m elements, where m is less than N, a vector generator for selecting a set of vectors {a i : i=1, . . . , n} each having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into said n assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for generating the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}; and a reconstructor for retrieving at least m of said assemblages from portions or components of said storage or memory system, and for reconstructing said information from said m retrieved assemblages, said reconstructor comprising a processor for forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m retrieved assemblages, a calculator for generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said m retrieved assemblages, and an assembler for reassembling the information from the thus generated N elements.

Claim 32

The apparatus of claim 23 wherein a fault or inaccessibility of a given portion or component does not necessarily also entail a fault or inaccessibility of another said portion or component.

Claim 33

Apparatus for a process for protecting against loss and enhancing speed of transmission on communication paths, of information which is represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational element, said communication links being prone to faults or congestions, said apparatus comprising a disperser for dispersing said information into n smaller assemblages, and for transmitting said n assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, in a manner that is expected to yield no fewer than a required number, m, of said assemblages, said disperser comprising a converter for representing said information by N elements of a field or computational structure, a segmenter for grouping said N elements into N/m groups of m elements, where m is less than N, a vector generator for selecting a set of vectors {a i : i=1, . . . , n} each having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into said n assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for generating the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}; and a reconstructor for receiving at least m of said assemblages from said, paths and for reconstructing said information from said m received paths, said reconstructor comprising a processor for forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m received assemblages, a calculator for generating the N elements which represent of the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said m received assemblages, and an assembler for reassembling the information from the thus generated N elements.

Claim 34

Apparatus for a process for protecting against loss and enhancing speed of transmission on communication paths, of information which is represented as data signals on communication paths, said information comprising data elements, each said data element representable as an element of a finite field or computational element, said communication links being prone to faults or congestions, said apparatus comprising a disperser for dispersing said information into n smaller assemblages, and for transmitting said n assemblages in the form of said data signals carried on multiple communication paths, or by transmitting said smaller assemblages at different times in the form of said data signals carried on a single communication path, in a manner that is expected to yield no fewer than a required number, m, of said assemblages, said disperser comprising a converter for representing said information by N elements of a field or computational structure, a segmenter for grouping said N elements into N/m groups of m elements, where m is less than N, a vector generator for selecting a set of vectors {a i : i=1, . . . , n} each having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into said n assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for generating the n assemblages such that the i th assemblage comprises the elements {c i ,r : r=1, . . . , N/m}; and a reconstructor for receiving at least m of said assemblages from said, paths and for reconstructing said information from said m received paths, said reconstructor comprising a processor for forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m received assemblages, a calculator for generating the N elements which represent of the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said m received assemblages, and an assembler for reassembling the information from the thus generated N elements.

Claim 35

The apparatus of claim 25 wherein a fault or congestion of a given link at a given time does not necessarily also entail a fault or congestion of said given link at another time or a fault or congestion of another said link.

Claim 36

Apparatus for protecting against loss and for enhancing accessibility in storage or memory, and protecting against loss and enhancing speed of transmission in a network, or information which is represented in storage or memory and represented as data signals on said network, said network and storage or memory being part of a distributed processing system of the kind having nodes with associated storage or memory devices, said nodes being interconnected in said network, and in which said storage or memory devices are prone to faults or inaccessibilities, said apparatus comprising a disperser for dispersing said information into n smaller assemblages, and for distributing said n assemblages to said storage or memory devices at different said nodes via said network, said disperser comprising a converter for representing said information by N elements of a field or computational structure, a segmenter for grouping said N elements into N/m groups of m elements, where m is less than N, a vector generator for selecting a set of vectors {a i : i=1, . . . , n} each having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into said n assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for generating the n assemblages such that the i th piece is an assemblage of the elements {c i ,r : r=1, . . . , N/m}; and a reconstructor for retrieving at least m of said assemblages from said storage or memory devices via said network, and for reconstructing said information from said m retrieved assemblages, said reconstructor comprising a processor for forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m retrieved assemblages, a calculator for generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said m retrieved assemblages, and an assembler for reassembling the information from the thus generated N elements.

Claim 37

Apparatus for protecting against loss and for enhancing accessibility in storage or memory, and protecting against loss and enhancing speed of transmission in a network, or information which is represented in storage or memory and represented as data signals on said network, said network and storage or memory being part of a distributed processing system of the kind having nodes with associated storage or memory devices, said nodes being interconnected in said network, and in which said storage or memory devices are prone to faults or inaccessibilities, said apparatus comprising a disperser for dispersing said information into n smaller assemblages, and for distributing said n assemblages to said storage or memory devices at different said nodes via said network, said disperser comprising a converter for representing said information by N elements of a field or computational structure, a segmenter for grouping said N elements into N/m groups of m elements, where m is less than N, a vector generator for selecting a set of vectors {a i : i=1, . . . , n} each having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, a calculator for calculating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into said n assemblages, each element c i ,r being calculated as the product of a vector a i times the elements of the r th said group of elements, and an assembler for generating the n assemblages such that the i th piece is an assemblage of the elements {c i ,r : r=1, . . . , N/m}; and a reconstructor for retrieving at least m of said assemblages from said storage or memory devices via said network, and for reconstructing said information from said m retrieved assemblages, said reconstructor comprising a processor for forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to calculate the elements c i ,r of the m retrieved assemblages, a calculator for generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of said m retrieved assemblages, and an assembler for reassembling the information from the thus generated N elements.

Claim 38

The apparatus of claim 27 wherein a fault or inaccessibility of a given storage device does not necessarily also entail a fault or inaccessibility of another said storage device.

Claim 39

Apparatus for communicating information packets among the nodes of a parallel processing computer, each node having an associated processor and memory, said nodes being linked by an interconnection network, whereby each node can communicate with any other node via paths at least some of which pass through intermediate nodes, said paths being subject to failure, and each said node's memory having a finite capacity, each information packet being sent from a source node to a destination node, said information packet comprising data elements, each said data element representable as an element of a finite field or computational structure, said apparatus comprising a disperser for transforming and breaking apart said information packet into n assemblages, and for sending said assemblages via different said paths of said network toward said destination node the transforming and breaking apart being done in accordance with the following method, by representing said information packet by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r-th said group of elements, and assembling the n pieces such that the i-th assemblage comprises the elements {c i ,r : r= 1 , . . . , N/m}, and a reconstructor for receiving at said destination node at least said m assemblages from said network, and for reconstructing said information packet from said m assemblages by forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to form the elements c i ,r of the available m assemblages, generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of the m available assemblages, and reassembling the information from the thus generated N elements.

Claim 40

Apparatus for communicating information packets among the nodes of a parallel processing computer, each node having an associated processor and memory, said nodes being linked by an interconnection network, whereby each node can communicate with any other node via paths at least some of which pass through intermediate nodes, said paths being subject to failure, and each said node's memory having a finite capacity, each information packet being sent from a source node to a destination node, said information packet comprising data elements, each said data element representable as an element of a finite field or computational structure, said apparatus comprising a disperser for transforming and breaking apart said information packet into n assemblages, and for sending said assemblages via different said paths of said network toward said destination node the transforming and breaking apart being done in accordance with the following method, by representing said information packet by N elements of said field or computational structure, grouping said N elements into N/m groups, each containing m elements, where N is greater than m, and hence there are more than one of said groups, selecting a set of vectors {a i : i=1, . . . , n}, each of said vectors having m elements of said field or computational structure, there being an arbitrarily high probability that any subset of m of the vectors are linearly independent, generating a set of elements {c i ,r : i=1, . . . , n, r=1, . . . , N/m} for assembly into n said assemblages, each element c i ,r being generated as the product of a vector a i times the elements of the r-th said group of elements, and assembling the n pieces such that the i-th assemblage comprises the elements {c i ,r : r= 1 , . . . , N/m}, and a reconstructor for receiving at said destination node at least said m assemblages from said network, and for reconstructing said information packet from said m assemblages by forming m vectors {α i : i=1, . . . , m} derived from the m vectors a i that were used to form the elements c i ,r of the available m assemblages, generating the N elements which represent the information by multiplying said vectors α i times vectors of length m formed by taking corresponding single elements, one from each of the m available assemblages, and reassembling the information from the thus generated N elements.

Claim 41

The apparatus of claim 29 wherein a failure or congestion of a given path at a given time does not necessarily also entail a failure or congestion of said given path at another time or a failure or congestion of another path.