Recent Research
-
Digital Fountain --
The proliferation of applications that must reliably distribute bulk data
to a large number of autonomous clients motivates the design of new multicast
and broadcast protocols. We describe an ideal, fully scalable
protocol for these applications that we call a digital fountain.
A digital fountain allows any number of heterogeneous clients to acquire bulk data
with optimal efficiency at times of their choosing. Moreover, no feedback channels
are needed to ensure reliable delivery, even in the face of high loss rates.
We develop a protocol that closely approximates a digital fountain based on
Tornado codes that are orders of magnitude faster than standard erasure codes
(see below for a description of Tornado codes).
We provide performance measurements that demonstrate
the feasibility of our approach and discuss the design,
implementation and performance of an experimental system.
A full description of this approach as appears in
ACM SIGCOMM '98
can be found in
A Digital Fountain Approach to Reliable Distribution of Bulk Data
(372K postscript). A related approach is to use Tornado Codes to speed up
downloads by accessing multiple mirror sites in parallel. This work is described
in
Accessing Multiple Mirror Sites in Parallel:
Using Tornado Codes to Speed Up Downloads (278K postscript)
-
Tornado Codes -- These revolutionary new erasure codes have
super-fast encoding and decoding algorithms. Some of the theory
behind Tornado codes is explained in
Practical Loss-Resilient Codes (177K postscript).
A slicker way to analyze these codes can be found in
Analysis of Random Processes via And-Or Tree Evaluation
(197K postscript).
You can read about some of their uses and characteristics
at this site.
Software-based implementations of Tornado codes are about 100 times faster
on small lengths and about 10,000 times faster on larger lengths
than other software-based Reed-Solomon erasure codes.
-
Slides that describe Tornado codes and their applications in
a digital fountain can be found
here (104K postscript).
-
Cauchy-based Reed-Solomon codes are available for
download here.
To understand the theory behind these codes, see the paper
titled
An XOR-Based Erasure-Resilient Coding Scheme (237K).
These erasure codes are based on traditional Reed-Solomon codes,
and are implemented in a way that makes them run reasonably fast
using a reasonable amount of memory.
They were developed in 1993-1994 for use in the
PET project at ICSI,
and are fast enough to run on real-time on small lengths.
What you will find when you click on "download" is a file,
which is the "uuencoding" of the "tar" of the directory containing
all the needed C source code.
You will need to "uudecode" and then extract the directory
using "tar xf tarcauchy" to create a directory called "CAUCHYCODE" with all
the appropriate files. The uunencoded file is only 144K bytes.
-
Benchmark comparisons of software implementations
of
- Tornado codes
- Cauchy-based Reed-Solomon codes
- Vandermonde-based Reed-Solomon codes
are available here.
Recent Activities
-
Program chair of and invited speaker to the upcoming
RANDOM'98 workshop,
to be held October 8-10, 1998 in Barcelona, Spain.
-
Invited speaker at Mathematisches Seminar der Universitat Kiel,
September 5-8, 1998, Kiel, Germany.
-
Invited minisymposium speaker in Randomized Algorithms session
at the
Ninth SIAM Conference on Discrete Mathematics,
July 12-15, 1998 in Toronto, Canada.
-
Invited speaker in Channel Coding Theory session at the
IEEE Information Theory Workshop,
February 8-11, 1998.
The abstract of the talk can be found here.
-
Guest editor of
Random Structures and Algorithms.
Volume 11, Number 4, December 1997.
Special issue dedicated to the
Randomness and Computation Workshop held at UC Berkeley
in December, 1995.
Recent Papers
-
Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads
(278K)
John Byers, Michael Luby, Michael Mitzenmacher,
appears as ICSI Technical Report TR-98-021, July 1998,
and has been submitted to
IEEE INFOCOM '99.
-
A Digital Fountain Approach to Reliable Distribution of Bulk Data
(372K)
John Byers, Michael Luby, Michael Mitzenmacher, Ashu Rege
appears in proceedings of
ACM SIGCOMM '98,
September 2-4, 1998.
-
Improved Low-Density Parity-Check Codes Using Irregular Graphs
and Belief Propagation (69K)
Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman
appears in the proceedings of the
1998 IEEE International Symposium
on Information Theory, August 16-21, 1998.
-
Analysis of Low Density Codes and Improved Designs Using Irregular Graphs
(207K)
Michael G. Luby, Michael Mitzenmacher,
M. Amin Shokrollahi, Daniel A. Spielman
appears in the proceedings of the
30th ACM STOC, May 23-26 1998.
-
Analysis of Random Processes via
And-Or Tree Evaluation (197K postscript)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi,
appears in the proceedings of
9th Annual ACM-SIAM Symposium on Discrete Algorithms,
January 25-27, 1998, San Francisco, California.
(125K postscript)
Publications
Click here
to see the other side of Luby