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

Bob Harris bob.harris.spamcontrol at gmail.com
Mon Mar 20 20:11:50 UTC 2006


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. 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?
Did I really see simulations talking about 40+ hops? Are these people
serious ? Do they not understand the difference between 5 hops and 25?
6 and 36?

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.  While
at it, one might as well read a recent P2P paper on O(log N),
O(d N ^ 1/d) or even O(1) systems. Why would anyone want to
reinvent a crappier wheel ?

Bob.

On 3/20/06, Ian Clarke <ian at locut.us> wrote:
> I think for the purposes of this conversation, around 70% will be
> more than sufficient (although without further thought I am not sure
> exactly how scalability in a small world network is affected by
> having variable numbers of links among nodes).
>
> Ian.
>
> On 20 Mar 2006, at 10:33, Greg Bildson wrote:
>
> > Define "most".  If you mean more than 70% (not sure of the exact
> > percentage), I would have to disagree.
> >
> > Thanks
> > -greg
> >
> >> -----Original Message-----
> >> From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-
> >> bounces at zgp.org]On
> >> Behalf Of Daniel Stutzbach
> >> Sent: Monday, March 20, 2006 1:29 PM
> >> To: Peer-to-peer development.
> >> Subject: Re: Dijjer and Freenet (RE: [p2p-hackers] clustering)
> >>
> >>
> >> On Mon, Mar 20, 2006 at 10:20:02AM -0800, Serguei Osokine wrote:
> >>>     You mean you did not expect to grow Dijjer and Freenet beyond
> >>> 512K nodes before you'd have to replace all the client code? With
> >>> today's P2P network sizes it might be a good idea to have the code
> >>> that would be ready to scale into high millions at least - you never
> >>> know when you might need it... :-)
> >>
> >> Most users upgrade their software within 2 months [1], so replacing
> >> all the client code actually isn't that hard.  I'm assuming the
> >> network is robust enough to keep working if a small percentage of
> >> clients have the old code.
> >>
> >> [1] = based on measurements of LimeWire Ultrapeer users.  Amir
> >> H. Rasti, Daniel Stutzbach, Reza Rejaie, "On the Long-term Evolution
> >> of the Two-Tier Gnutella Overlay", to appear at the Global Internet
> >> Symposium 2006.
> >>
> >> --
> >> Daniel Stutzbach                           Computer Science Ph.D
> >> Student
> >> http://www.barsoom.org/~agthorr                     University of
> >> Oregon
> >> _______________________________________________
> >> p2p-hackers mailing list
> >> p2p-hackers at zgp.org
> >> http://zgp.org/mailman/listinfo/p2p-hackers
> >> _______________________________________________
> >> Here is a web page listing P2P Conferences:
> >> http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
> >
> >
> > _______________________________________________
> > p2p-hackers mailing list
> > p2p-hackers at zgp.org
> > http://zgp.org/mailman/listinfo/p2p-hackers
> > _______________________________________________
> > Here is a web page listing P2P Conferences:
> > http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
> >
>
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers
> _______________________________________________
> Here is a web page listing P2P Conferences:
> http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
>



More information about the P2p-hackers mailing list