[p2p-hackers] Chord comments
Carl Bosley
bosley at hcs.harvard.edu
Mon Sep 3 17:46:01 UTC 2001
> > My math is probably naive or just wrong, but my attempt at probability
> > says that your probability of having the closest key is
> > (evil / (good + evil)) ^ keys.
> So the chance of getting at least one dart in each of P specific bins
> (places), given M honest machines already in the ring and given N darts
> (new IPs) that you can try, is:
>
> sum over i from 0 to P of
> (-1)^i * (P Choose i) * ((M-i)/M)^N
indeed.
if you'd like something easier to approximate ... note for P = 1 this is
1 - ((M-1)/M)^N
~= 1 - e^{-N/M}
For P > 1, for N >> 1 the overlap is negligible enough that
(1 - e^{-N/M})^P
is a good approximation.
--Carl
More information about the P2p-hackers
mailing list