Dijjer and Freenet (RE: [p2p-hackers] clustering)
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
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.
More information about the P2p-hackers