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

Daniel Brookshier turbogeek at
Mon Mar 20 21:14:32 UTC 2006

I'll chime in. In the P2P world, O(log^2 N) may not be efficient, but  
it may be the cheapest in terms of resources. 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. Conversely, to attain fewer hops,  
that also means a larger resource at each node to index and process  
the index queries. There are also ways to use the hubs in such  
networks to greatly improve efficiency.

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.

On Mar 20, 2006, at 2:42 PM, Ian Clarke wrote:

> On 20 Mar 2006, at 12:11, Bob Harris wrote:
>> There is a lot of hype around small world networks. They have
>> a catchy name. And they are easy to code up. But they have terrible
>> performance.
> It is rather courageous (or perhaps simply foolish) of you to  
> dismiss an entire avenue of study so cavalierly, time will tell  
> whether you are right.
>>  Who wants O(log^2 N) performance?
> It has already been pointed out that actual route lengths are far  
> more important than the order of the route lengths in practical  
> networks.  It has also been pointed out that O(log^2 N) performance  
> presumes a fixed routing table size, where in most if not all  
> practical deployments, routing table sizes are increased with the  
> size of the network.
>> Did I really see simulations talking about 40+ hops?
> You might have, but I can't recall any such simulations mentioned  
> in this thread.
> Ian.
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at
> _______________________________________________
> Here is a web page listing P2P Conferences:

More information about the P2p-hackers mailing list