Excavating
Patent
1991-05-15
1996-01-16
Baker, Stephen M.
Excavating
371 391, 371 401, H03M 1300
Patent
active
054854741
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.
REFERENCES:
Blakley, G., "Safeguarding Cryptographic Keys", AFIPS Conf. Proc., vol. 48, 1979, pp. 313-317.
Blakley, G., "One-Time Pads are Key Safeguarding Schemes, Not Cryptosystems . . . ", Proc. 1980 Symp. on Security and Privacy, pp. 108-113.
Asmuth, Blakley ("Pooling, Splittting, and Restituting Information to Overcome Total Failure of some Channels of Communications", Proc. of the 1982 Symp. on Security and Privacy, IEEE, 1982, pp. 156-169).
Rabin ("Fingerprinting by Random Polynomials", TR-15-18, Center for Research in Computing Technology, Harvard Univ., Cambridge, Mass., 1981).
Blakley, Meadows ("Security of Ramp Schemes", Proc. of CRYPTO, 1984, pp. 242-268).
Pippenger ("Parallel Communication with Limited Buffers", IEEE 25th Symp. on FOCS, 1984, pp. 127-136).
Rabin ("Probabilistic Algorithms in Finite Fields", SIAM J Compt., vol. 9, 1980, pp. 273-280).
Shamir ("How to Share a Secret", Comm. ACM, vol. 22:11, 1979, pp. 612-613).
Valiant ("A Scheme For Fast Parallel Communication", SIAM J. Compt., vol. 11:2, 1982, pp. 350-361).
Rao, T., "Joint Encryption and Error Correction Schemes", Proc. 10th Int'l. Symp. on Computer Architecture, Computer Society Press, pp. 240-241, 1984.
Kahn, R., "The Organization of Computer Resources into a Packet Radio Network", IEEE Trans on Communications, vol. COM-25, No. 1, Jan. 1977, pp. 169-177.
Wu, W., Elements of Digital Satellite Communications, vol. II: Channel Coding and Integrated Services Digital Satellite Networks, Computer Science Press, 1985, pp. 158-171.
Meyer, C. et al., Cryptography: A New Dimension in Computer Data Security, John Wiley & Sons, 1982, pp. 212-213.
McEliece et al., "On Sharing Secrets and Reed-Solomon Codes", Commun. of the ACM, vol. 24, No. 9, Sep. 1981, pp. 583-584.
Karnin et al., "On Secret Sharing Systems", IEEE Trans. on Information Theory, vol. IT-29, No. 1, Jan. 1983, pp. 35-41.
Baker Stephen M.
The President and Fellows of Harvard College
LandOfFree
Scheme for information dispersal and reconstruction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheme for information dispersal and reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for information dispersal and reconstruction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-315015