Big hype on small worlds. (was Re: Dijjer and Freenet (RE: [p2p-hackers] clustering))

Bob Harris bob.harris.spamcontrol at
Mon Mar 20 21:39:24 UTC 2006

> In the P2P world, O(log^2 N) may not be efficient, but
> it may be the cheapest in terms of resources.

I like the use of "may" in that sentence. Well, maybe not. Small worlds
typically need O(log N) connections to other nodes to maintain
connectivity. Pastry and Chord use O(log N) connections as well. Small
worlds get O(log^2 N) hop lookups, Pastry and Chord get O(log N).
Remind me how x^2 packets and x^2 processing is better than x.

>For instance, a walker
> may take a while to find a resource in a small world topology, but it
> expends little effort at each node.

Same arguments apply to a Chord or Pastry lookup. The bandwidth
spent to retain the ring structure is about the same as the bandwidth
spent to ping neighbors.

>Conversely, to attain fewer hops,
> that also means a larger resource at each node to index and process
> the index queries.

True only in unstructured networks. Indexing and aggregation
of the kind you allude to are not necessary to get better lookup
times in structured p2p.

>There are also ways to use the hubs in such
> networks to greatly improve efficiency.

Same techniques to reduce N apply equally well to other systems.

> The small world is also not necessarily the complete network or only
> topology available to an application. The number of hops in a search
> is not the same as a the number of hops that may be applied to
> communications. Thus even when one part is inefficient, the other may
> be ideal.

True, when something doesn't work well, there are other ways around
it. I see nothing but hype in small worlds. Why not add UDDI+WSDL+
web services+social networking and become buzzword complete?

How many here realize that the hype around small worlds was
created mostly by physicists by applying elementary math to a highly
idealized and theoretical problem, with no implementation? Those guys
don't care about performance, just the pretty name. You've all seen
the books, and you know they are devoid of content. 5 is really << 25.
Use the better tool.


More information about the P2p-hackers mailing list