[ont.events] U of Toronto Computer Science seminar, Nov. 29

clarke@csri.toronto.edu (Jim Clarke) (11/19/88)

     THEORY SEMINAR - Tuesday, November 29,  3 p.m.  in  Room  GB 221
              (GB = Galbraith Building, 35 St. George Street)

                             Michael O. Rabin
           Professor of Computer Science Harvard University and
      Professor of Mathematics and Computer Science Hebrew University

      "Efficient Dispersal of Information for Security Load Balancing
                           and Fault Tolerance"

We develop an Information Dispersal Algorithm (IDA) which breaks a file F
of length L = |F| into n pieces of Fi, 1 <= i <= n, each of length | Fi| = L/m,
so that every m pieces suffice for reconstructing F.  Dispersal and
reconstruction are computationally effient.  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 we get
provably time efficient and highly fault-tolerant routing on the n-cube, using
just constant size buffers.
-- 
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
              (416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu     CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke