Michael O. Rabin
Abstract
An Information Dispersal Algorithm (IDA) is developed that breaks a file F of length L = ↿ F↾ into n pieces Fi, l ≤ i ≤ n, each of length ↿Fi↾ = L/m, so that every m pieces suffice for reconstructing F. Dispersal and reconstruction are computationally efficient. The sum of the lengths ↿Fi↾ is (n/m) · L. Since n/m can be chosen to be close to l, the IDA is space efficient. IDA has numerous applications to secure and reliable storage of information in computer networks and even on single disks, to fault-tolerant and efficient transmission of information in networks, and to communications between processors in parallel computers. For the latter problem provably time-efficient and highly fault-tolerant routing on the n-cube is achieved, using just constant size buffers.
- 1 ASMUTH, C. A., BLAKLEY, G.R. Pooling splitting and restituting information to overcome total failure of some channels of communication. In Proceedings of the 1982 Symposium on Security and Privacy. IEEE Society, New York, 1982, pp. 156-169.Google Scholar
- 2 BERLEKAMP, E.R. Algebraic coding theory. McGraw-Hill, New York, 1968.Google Scholar
- 3 HALL, M. Combinatorial Theory. Wiley, New York, 1980.Google Scholar
- 4 HILLIS, W.D. The Connection Machine. MIT Press, Cambridge, Mass., 1985. Google Scholar
- 5 MIRSKY, L. An Introduction to Linear Algebra. Dover, New York, 1982.Google Scholar
- 6 PIPPENGER, N. Parallel communication with limited buffers. In Proceedings of the IEEE 25th Symposium on Foundations of Computer Science. IEEE, New York, 1984, pp. 127-136.Google Scholar
- 7 RABIN, M.O. Probabilistic algorithms in finite fields. SIAM J. Comput. 9, 1980, 273-280.Google Scholar
- 8 RABIN, i.O. Fingerprinting by random polynomials. Tech. Rep. TR-15-81. Center for Research in Computing Technology. Harvard Univ., Cambridge, Mass., i 98 i.Google Scholar
- 9 RAGHAVAN, P. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. In Proceedings of the IEEE 27th Symposium on Foundations of Computer Science. lt:t:l:., r~ew York, i 986, pp. i 0- i 8. Google Scholar
- 10 SEITZ, C.L. The cosmic cube. Commun. ACM 28, 1 (Jan. 1985), 22-33. Google Scholar
- 11 SHAMIR, A. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612-613. Google Scholar
- 12 llzlilZL, 11. 3. /-~ rnotael Ol )IIVIL; macn}nes anu a companson of various interconnection networks. IEEE Trans. Comput. 28, 12 (1979), 907-917.Google Scholar
- 13 VALIANT, L. G. A scheme for fast parallel communication. SlAM J. Comput. 11, 2 (1982), 3g/-~ -lt-Google Scholar
Index Terms
- Efficient dispersal of information for security, load balancing, and fault tolerance
Recommendations
Efficient Byzantine Fault-Tolerance
We present two asynchronous Byzantine fault-tolerant state machine replication (BFT) algorithms, which improve previous algorithms in terms of several metrics. First, they require only 2f+1 replicas, instead of the usual 3f+1. Second, the trusted ...
Redundancy Does Not Imply Fault Tolerance: Analysis of Distributed Storage Reactions to File-System Faults
Special Issue on FAST 2017 and Regular PapersWe analyze how modern distributed storage systems behave in the presence of file-system faults such as data corruption and read and write errors. We characterize eight popular distributed storage systems and uncover numerous problems related to file-...
Fault tolerance on star graphs
PAS '95: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture SynthesisFault tolerance capability is one of the advantages of multiprocessor systems. We prove that the fault tolerance of star graphs is 2n-5 with restriction to the forbidden faulty set. We propose an algorithm for examining the connectivity of star graphs ...
Comments