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

[Daniel Stutzbach]

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
http://www.barsoom.org/~agthorr                     University of Oregon