[p2p-hackers] network coding put to practical p2p content dist. use

[Nick Johnson]

On 17/06/2005, at 5:30 PM, Alen Peacock wrote:

> Bram Cohen makes some interesting arguments against such a scheme:
> http://www.advogato.org/person/Bram/ (Nov 7 2004 entry, "erasure
> codes").

His arguments there are mostly specious. He states "One possible  
benefit erasure codes is that when sending data to a peer there are  
so many potential pieces that you can send any random one you have  
and it won't be a duplicate. The problem is that the peer may already  
have gotten that same piece from another peer, so that benefit is  
destroyed, and on top of that the overhead of communicating and  
remembering which peer has what is increased tremendously." - a  
blanket assertion which isn't true at all. Granted, there's still a  
chance that your peer already has the piece you want to send, but the  
higher the number of pieces, the lower that chance.

> I'm sure most p2p-hackers readers are familiar with this reasoning,
> but I'm equally convinced that a lot of us don't necessarily agree
> with Bram's stance, at least not in the general case.  At the same
> time, I don't think anyone would argue that the costs associated with
> using erasure codes inside a decentralized system (both in terms of
> implementation and processing) aren't significant.

Indeed. Personally, I think the main problem with Fountain codes and  
the like is the lack of an easy way to verify individual pieces.  
There exists a Homomorphic Hashing algorithm for the purpose, but  
it's complex, extremely slow, expands the encoded pieces (though not  
by much), and the hashes themselves are large. More development is  
needed here before it's a practical system, IMHO.

That said, I'm working on a P2P system where we do intend to use  
Online codes (a variant of Fountain codes) - not for piece encoding,  
but for the transmission of individual pieces via multicast. This is  
where they really shine.

-Nick Johnson