On Tuesday, March 21, 2006 Oskar Sandberg wrote:
> No theory. Your best bet is to simulate and see.
I seem to recall that you had a link to your simulations source
code somewhere in the previous mails, but I could not find it when
I looked. Is it a confabulation and there was no link, or I simply
missed it when looking?
Sorry to be such a pest, but I'm still trying to come to terms
with this phase transition thing at 1M and degree of 20. Intuitively
I have this feeling that the graph with this constant outdegree should
not disintegrate into unconnected pieces no matter what's its size,
and that phase transition should happen only if the links are truly
random and the outdegree of some nodes can be zero (or close to it)
as a result. Then sure, these nodes are simply not connected to anyone
and their queries all fail. I simply cannot picture the graph where
every node carefully monitors the number of its links, never allowing
their number to drop below 20, and the graph still breaks into many
components - the intuitive feeling is that as every node maintains
these 20 links, the probability of at least one of them leading to
the giant component should be very close to 1, and as we are adding
nodes, this should still remain the case, so all nodes should stay
clustered together.
I have this feeling that I'm not the only one on this list who
might have trouble visiualizing the phase transition, so maybe looking
at how it is happening in a real simulation would help.
By the way - could it be that the phase transition is due to
the unidirectional nature of the links? I mean, speaking in naive
terms: let's say that the graph breaks down into two components of
roughly the same size. Then as you add one more node to it, the
probability of this node connecting to both halves of the graph at
once is about (1 minus 2^(-19)). Then this node will become a bridge
between the graph components and glue them back together - but *only*
if the links are bidirectional. Unidirectional links won't act as a
"bridge", or "glue", and half of the graph still won't be able to
find anything in the other half.
So could it be the case that if the links are bidirectioonal
(a la Gnutella), you cannot have the phase transitions no matter
what - but if the links are unidirectional (like certain UDP-based
DHT implementaitons that I can imagine), you do have the phase
transition problem? And if so, does it mean that it is an extremely
good idea to make sure that all links are bidirectional and can
be used for searching, regardless of whether you establish them
yourself or receive as an incoming UDP packet from the previously
unknown node?
Best wishes -
S.Osokine.
21 Mar 2006.
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
Behalf Of Oskar Sandberg
Sent: Tuesday, March 21, 2006 1:17 PM
To: Peer-to-peer development.
Subject: Re: Big hype on small worlds. (wasRe: Dijjerand Freenet(RE:
[p2p-hackers] clustering))
Serguei Osokine wrote:
> On Tuesday, March 21, 2006 Oskar Sandberg wrote:
>
>>It could probably grow forever without having a phase transition.
>
>
> I sure hope so, but then the next question is, what should be
> the scaling factor k in "degree=k x log2(N)" for this to be the case?
> I mean, k=1 seems to be not enough - with k=1 you have a transition
> with 1M nodes (when your degree is 20), correct?
No theory. Your best bet is to simulate and see.
// oskar
_______________________________________________
p2p-hackers mailing list
p2p-hackers@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@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
