[p2p-hackers] gossiping in a DHT

[John Casey]

thanks guys. I've just been reading digesting the papers you have
given me. The structella, and the pointers to the broadcasting papers
it have are very useful :)

On Tue, 8 Feb 2005 05:31:56 -0800, Paul Campbell <paul at ref.nmedia.net> wrote:
> On Mon, Feb 07, 2005 at 07:22:30PM +1100, John Casey wrote:
> > Hi All, I have been thinking about developing a gossip information
> > dissemenation algorithm to work across a DHT. Does any one have any
> > links to any must read papers on this topic? Conceptually, the process
> > seems similar to that of gossip in an unstructured DHT. Just wondering
> > if there was any prior work I should take a look at thanks. :)
> 
> Gossipping has to overcome the unstructured nature of the underlying
> network. In a DHT, this is not necessary since it is easy to set up a
> real broadcast. Look for protocols dealing with broadcasting on a DHT.
> 
> For instance, one could propagate a message around the ring until it gets
> back to the source. This would take N-1 messages (if the originator is
> listed in the message) and N-1 rounds.
> 
> A faster way is to use the DHT structure where some nodes broadcast multiple
> messages. For instance, the source could conceptually break the DHT ring up
> into arcs and broadcast a message to a node residing on each arc along with
> the arc length. In turn, the next layer of nodes can broadcast the message
> across their respective arcs, subdividing the problem by another level. With
> log(N) known neighbors, it should take log(N) rounds to reach every node and
> again, N-1 messages. Contrast this with N*log(N) messages in an unstructured
> gossipping system with log(N) rounds. Thus, without structure, the load is
> much higher.