The Information Dispersal Algorithm and its Applications

Michael O. Rabin
Additional contact information
Michael O. Rabin: Harvard University, Aiken Computation Laboratory

A chapter in Sequences, 1990, pp 406-419 from Springer

Abstract: Abstract We present the Information Dispersal Algorithm (IDA) which breaks a file F of length L = |F| into n pieces F i , 1 ≤ i ≤ n, each of length |F i | = L/m, so that every m pieces suffice for reconstructing F. Dispersal and reconstruction are computationally efficient. The sum of lengths |F i | is (n/m) L. Since n/m can be chosen to be close to 1, 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. Here we also give applications to the problem of data consistency and availability in distributed systems, and to a distributed pattern matching algorithm.

Keywords: Buffer Size; Storage Overhead; False Match; Route Algorithm; Reliable Storage (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_32

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_32

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().