On Sat, Nov 01, 2003 at 06:25:45AM -0800, Martin Stone Davis wrote: > Matthew Toseland wrote: > > >Update of /cvsroot/freenet/freenet/src/freenet > >In directory sc8-pr-cvs1:/tmp/cvs-serv25429/src/freenet > > > >Modified Files: > > Version.java > >Log Message: > >6295: > >If HTL == maxHTL, 50% chance of not decrementing. I believe this > >converges to an extra 2 hops, somebody please check my math. This > >provides some plausible deniability when you send a request at max > >HTL (perturb runs only on client level...). > Nope, it's one extra hop. To make it two extra hops, you need to > increase the chance of not decrementing to 66.67%.
Cool. I didn't particularly want extra hops. I just wanted to fix the current behaviour, which is bad. > > EXPLANATION: > > Given a request at HTL==25, there's a 50% chance that it will > immediately decrement. There's a 25% chance that it will decrement > after 1 hop. There's a 12.5% chance that it will decrement after 2 > hops. 6.25% ... 3 hops, etc. > > So, in terms of expected # of extra hops, E: > > E=0.5*0 + > 0.25*1 + > 0.125*2 + > 0.0625*3 + > ... > =0.5*Sum[k=0 to infintiy,k*(0.5^k)] > =0.5*0.5/(1-0.5)^2 > =1 > > To derive that, I used the formula: > > Sum[k=0 to infinity,k*q^k] > = q/(1-q)^2, (for |q|<1) > > > So, if we want it to converge to 2 extra nodes, and q is the chance that > we don't decrement, we have to solve: > > 2=(1-q)*0 + > q*(1-q)*1 + > q^2*(1-q)*2 + > ... > =(1-q)*Sum[k=0 to infinity,k*q^k] > =(1-q)*q/(1-q)^2 > =q/(1-q) > > Solving for q: q=2/3. So, make the chance of not decrementing=2/3. > > -Martin > > > _______________________________________________ > Devl mailing list > [EMAIL PROTECTED] > http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl -- Matthew J Toseland - [EMAIL PROTECTED] Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so.
signature.asc
Description: Digital signature
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
