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

Daniel Stutzbach agthorr at
Mon Mar 20 21:47:09 UTC 2006

On Mon, Mar 20, 2006 at 04:39:24PM -0500, Bob Harris wrote:
> 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.

Pastry and Chord *are* small worlds, so I think you're a bit confused.

It sounds like you're generalizing based on some very specific network (which
you haven't named) that happens to also be a small world.

Daniel Stutzbach                           Computer Science Ph.D Student                     University of Oregon

More information about the P2p-hackers mailing list