[p2p-hackers] Online Codes

[Nick Johnson]

mgp at ucla.edu wrote:

>Hi Nick,
>
>First, I think your optimization to rateless codes is interesting,
>although I'm worried that it might not be 
>computationally feasible. I haven't given it much thought yet, but at
>first glimpse it seems like it would take 
>exponential or factorial time to come up with such shortcuts from XORing
>the check blocks. I'll give it more 
>thought, but if you or anyone else can show it can be done efficiently, I 
>will be pleasantly suprised :)
>  
>
As far as I can tell (though I can't prove it), it should be possible to 
reduce the magnitude as much as is possible by simply checking each 
received block against the ones already received. 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. At first glance this would reqire O(n) time per block, 
and hence O(n^2) time for all blocks, but it could probably be reduced 
by creating tree 'indexes' to the blocks that contain each source block, 
reducing the complexity to less than O(n) for each block.

>About your second e-mail... On the web site www.rateless.com, if you go
>to Library, you will see that under 
>the "Online Codes" paper it says:
>
>"This paper marked the beginning of Rateless Research. The codes
>described in it fall within the scope of 
>patents owned by Digital Fountain, Inc. In order to prevent intellectual
>property overlap, we have 
>developed and use a new class of practical rateless codes, based on
>decoders that don't use chain-reaction, 
>message passing or belief-propagation techniques."
>  
>
So Online codes should be unencumbered, while Torrent / LT codes aren't?

-Nick Johnson