Dijjer and Freenet (RE: [p2p-hackers] clustering)

Serguei Osokine Serguei.Osokine at efi.com
Mon Mar 20 17:32:57 UTC 2006


On Monday, March 20, 2006 Oskar Sandberg wrote:
> Phase transitions are a very common phenomenon in the study of 
> random graphs.

	Interesting. Is there any way to predict these things in
advance and stick to the networks that do not have this problem? 
I mean, running the simulations with the number of nodes increasing
all the way into millions is not the best method of assuring the
future network operation. Among other things, your simulation might
simply miss the phase transition for whatever reason.

	With Gnutella, for example, we knew that the problem was there 
two months before the actual meltdown, and simple back of the napkin
calculations were sufficient to see that. And once it was fixed, the
network grew into the millions of nodes without any further issues.
Is this kind of prediction possible here? This phase transition (and
the reason for it) were not intuitively obvious and expected - at 
least for me. In fact, I'd still be hard-pressed to explain it, even
with the knowledge that it is expected.

> No, it isn't a bug. In fact, I was expecting it at some point, 
> I just didn't know where for this particular case. You cannot 
> compare this to Chord, it is a much richer, more complex, 
> probabilistic model.

	So what you're saying is that once Dijjer approaches one million
nodes, it will have a catastrophic meltdown? And this is the way it is
supposed to be? What about Freenet? Will it blow up before reaching 
one million nodes as well? And if yes, can you do something to prevent
it? 

	Best wishes -
	S.Osokine.
	20 Mar 2006.


-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org]On
Behalf Of Oskar Sandberg
Sent: Monday, March 20, 2006 2:49 AM
To: osokin at osokin.com; Peer-to-peer development.
Subject: Re: Dijjer and Freenet (RE: [p2p-hackers] clustering)


Serguei Osokine wrote:
> On Sunday, March 19, 2006 Oskar Sandberg wrote:
> 
>>...the network with 20 links undergoes a phase transition between
>>500 thousand and one million nodes, after which it doesn't work 
>>at all (this behavior isn't surprising).
> 
> 
> 	It is to me. How come it is significantly more than square, 
> and doubling of the number of nodes increases the path by a factor 
> of *thirty*?

Like I said, it means that the network has undergone a phase transition 
to a completely different behavior. At some point the number of edges 
compared to the size is not sufficient to keep the network connected 
enough, and the whole thing breaks down. Phase transitions are a very 
common phenomenon in the study of random graphs.

> 	If I understand things correctly, Chord, for example, would have
> about 19 steps at 512,000 (with 19 links, mind you), and 20 steps at
> one million - having the same 20 links that your simulation of Dijjer
> does. This result of 472 is *extremely* counterintuitive (I'd expect
> to see 19-20 at most), and desrves some explanation. Frankly, at the
> absence of other data, the simulation bug seems to be the most likely
> explanation. 

No, it isn't a bug. In fact, I was expecting it at some point, I just 
didn't know where for this particular case. You cannot compare this to 
Chord, it is a much richer, more complex, probabilistic model.

// oskar
_______________________________________________
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