[p2p-hackers] Online Codes

[Bryan Turner]

Nick,

> If the number of source blocks they don't share is fewer than the order
> of whichever of the two blocks has higher order, replace the higher order
> block with the xor of the two.

	You are correct, this will work for codes which use XOR.  I share
Michael's caution about the efficiency of this scheme, as most packets will
be sourced from dozens of blocks.  With indexing, this could be sub-linear
per application - but is an application per source block, or per packet?  My
guess is that even the best indexing would still require per-source-block
lookup.  So you have dozens of sub-linear applications per packet, which
will probably end up being super-linear if your big-O constants aren't very
small.

	If you could keep the DAG of all source blocks, received packets,
etc, in memory then you could reduce it to O(M) per application where M is
the depth of the DAG.  But there's some recursion that's not accounted for
at the next layer so the total cost is more than O(nM), it would be like
O(n*CM) where C is the recursion constant.

> So Online codes should be unencumbered, while Torrent / LT codes aren't?

	As far as I am aware, Digital Fountain owns all the patents to
rateless codes currently in the literature.  This is dangerous territory for
open-source.  That makes Rateless.com's claims of an unencumbered rateless
code even more interesting.. their product documentation uses the words
"Mixed Acyclic Decoder", which I cannot find any other references to online.

	My guess is that they have generalized the connectivity DAG for the
source packets ("acyclic"), and used a two-part code ("mixed") to regenerate
the DAG at the other end.  Most of the Digital Fountain IP is predicated on
the small per-packet ID-tag which identifies the connectivity of the packet
in the source DAG.  Digital Fountain has been working to optimize the source
DAG to reduce memory consumption and improve throughput (basically you have
to keep the entire file in memory to run a Digital Fountain of it).
Rateless has probably come up with a new ID-tag which does not read on the
Digital Fountain IP, but transmits the same information.

--Bryan
bryan.turner at pobox.com