• 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.
  
  

• Pseudorandomness and Cryptographic Applications, a monograph published by Princeton University Press, approximately 250 pages
• Pairwise Independence and Derandomization, a survey paper joint with Avi Wigderson written in the summer of 1995, approximately 60 pages.
• Publications by Category (available papers are in postscript):
  • Real-Time Coding
  • Transmission Protocols
  • Parallel and Distributed Computation
  • Cryptography and Security
  • Derandomizing Algorithms
  • Monte Carlo Algorithms for Hard Counting Problems
  • Self-Testing/Correcting Programs
  • Optimal Simulation
  • Neural and Belief Networks
  • Online Algorithms

Click here to see the other side of Luby