[p2p-hackers] DHT or unstructured?

[Wolfgang Müller]

On Thursday 07 July 2005 02:35, Michael J. Freedman wrote:
> At the latest NSDI, Castro et al had a paper "Debunking some myths about
> structured and unstructured overlays" that argued that 'anything
> unstructured systems can do, structured systems can do better'.
>
>    http://www.research.microsoft.com/~antr/MS/myths.pdf

>
> Basically, it wasn't providing specific algorithms, e.g., for prefix
> search as Sean suggested, but instead suggesting that you can leverage the
> structure for other than DHT queries.  For example, (1) if you want a very
> rich query language -- which is the main reason people suggest using
> unstructured systems -- you can always improve performance by using the
> structured overlay to _direct_ the query, as opposed to random walks.

In the same vein, it is often overlooked that even *shipping* complex 
similarity queries is expensive, even if the peer reached does not contribute 
a result. The Li et al. paper 

 http://pdos.csail.mit.edu/~rtm/papers/search_feasibility.ps

assumes a bandwidth budget of about 1 megabyte per query. You can easily spend 
all that by shipping a 1000byte query to 1000 peers, so you're really tight 
on how much you are going to spend even disseminating the query.

A first step towards reducing that communication cost is doing broadcast in a 
structured overlay (which contacts each peer once) instead of Gnutella-like 
flooding (which contacts each peer multiple times).

Best,
Wolfgang
-- 
Dr. Wolfgang Müller
LS Medieninformatik
Universität Bamberg
Check out the SIG MM web site http://www.sigmm.org