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

coderman coderman at
Mon Mar 20 20:28:08 UTC 2006

On 3/20/06, Bob Harris <bob.harris.spamcontrol at> wrote:
> Hi everyone,
> Having lurked on this list for some time, I discern an interesting
> trend. 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...

back in 2000: s/small world/peer to peer/g.  like any fad this has
merit and hyperbole. (as will the next technology/idea, and the next,

> ... I suspect most people who work on small worlds are
> either theoreticians who don't care about performance, or innumerate
> people caught up in the hype. Who wants O(log^2 N) performance?

this varies a _lot_ based on architecture; besides, not everyone wants
to scale a small world to 500,000,000 users.

> Those of you who are puzzled by phase transitions ought to read Karp's
> paper "The Transitive Closure of a Random Digraph," Random Structures
> and Algorithms, Vol. 1, No. 1 (1990). He shows that you need log N
> edges per node on average to keep a random graph connected.

homogeneous, yes. which is why the paper on inhomogeneous random
graphs is useful.  the real world is not homogeneous...

better understanding of the elements in your decentralized networking
toolkit gives better product.

(that said i do agree that far too many designs overlook the impact of
malicious/coordinated attacks on these fragile overlay/routing

More information about the P2p-hackers mailing list