[p2p-hackers] gossiping in a DHT

[Paul Campbell]

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.