[p2p-hackers] gossiping in a DHT

[Alexander Löser]

Hi John,
probably you should look at the hypercup topology [1] , that permits broadcasting
in a structured overlay. In Edutella [2] we use the broadcast mechanism to
broadcast complex queries. Due to the combination of the broadcast with routing
indices and a super-peer network  we are able to focus the broadcast to a subset
of peers.

Alex

[1]
http://projekte.learninglab.uni-hannover.de/pub/bscw.cgi/d7825/HyperCuP%20-%20Hypercubes,%20Ontologies%20and%20Efficient%20Search%20on%20P2P%20Networks

[2]
http://www.kbs.uni-hannover.de/Arbeiten/Publikationen/2002/www2003_superpeer.pdf



John Casey wrote:

> 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.
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers
> _______________________________________________
> Here is a web page listing P2P Conferences:
> http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences

--
___________________________________________________________

  Alexander Löser
  Technische Universität Berlin
  http://cis.cs.tu-berlin.de/~aloeser/
  office : +49- 30-314-25551
  fax    : +49- 30-314-21601
___________________________________________________________