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

Oskar Sandberg ossa at math.chalmers.se
Mon Mar 20 10:49:22 UTC 2006

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

More information about the P2p-hackers mailing list