Title: Online Codes 

(NYU-CS-TR833)

Author: Petar Maymounkov 

Abstract:
We introduce online codes - a class of near-optimal codes for a very general
loss channel which we call the free channel. Online codes are linear encoding /
decoding time codes, based on sparse bipartite graphs, similar to Tornado codes,
with a couple of novel properties: local encodability and rateless-ness. Local
encodability is the property that each block of the encoding of a message can
be computed independently from the others in constant time. This also implies
that each encoding block is only dependent on a constant-sized part of the
message and a few preprocessed bits. Rateless-ness is the property that each
message has an encoding of practically infinite size.

We argue that rateless codes are more appropriate than fixed-rate codes for most
situations where erasure codes were considered a solution. Furthermore, rateless
codes meet new areas of application, where they are not replaceable by
fixed-rate codes. One such area is information dispersal over peer-to-peer
networks.