Scheme for information dispersal and reconstruction

Abstract

Method and apparatus applicable to a variety of data storage, data communication, and parallel computing applications, efficiently improving information availability and load balancing. Information to be transmitted in a data signal or stored is represented as N elements of a field or computational structure, and dispersed among a set of n pieces that are to be transmitted or stored in a manner yielding no fewer than m pieces used in subsequent reconstruction. For dispersal, n vectors a.sub.i each having m elements are used and the n pieces are assembled from elements obtained as products of these vectors with m element groups taken from the N elements representing the information. For reconstruction from m available pieces, m m-element vectors .alpha..sub.i are derived from the vectors a.sub.i, and the N elements representing the information are obtained as products of these vectors with m-element groups taken from the pieces. The vector products may be implemented using an appropriate processor, including a vector processor, systolic array, or parallel processor. For fault-tolerant storage in a partitioned or distributed system, information is dispersed into n pieces so that any m suffice for reconstruction, and the pieces are stored in different parts of the medium. For fault-tolerant and congestion-free transmission of packets in a network or a parallel computer, each packet is dispersed into n pieces so that any m pieces suffice for reconstruction and the pieces are routed to the packet's destination along independent paths or at different times.