[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