Correctness proof for new bandwidth-weights (bug 1952)

[Mike Perry]

Thus spake Mike Perry (mikeperry at fscked.org):
 
> Case 2b:
> 
>   Wgg = Wee = weight_scale
>   Wed = (weight_scale*(D - 2*E + G + M))/(3*D)
>   Wmd = (weight_Scale*(D - 2*M + G + E))/(3*D)
>   Wme = Wmg = 0
>   Wgd = weight_scale - Wed - Wmd
>
> Wmd >= 0:
>   D+G+E-2*M >= 0
    D+G+E-2*M+M >= M
    D+G+E+M >= 3*M
>   T/3 >= M
> 
>   If your eyes haven't glazed over yet, you'll notice that this last
>   condition can actually be true. If we don't hand out enough Guard

*sigh*... And, of course by "true" here, I actually meant "false", in
that there can be mathematical situations where M > T/3 and this
weight could thus take on a negative number. The rest of this
paragraph was correct, I just said "true" when I meant "false".

>   flags, there may be too many middle nodes. In this case, the code just
>   warns and suggests that the WFU parameters be lowered.

The code also sets this weight to 0 in this case, and adjusts Wgd
appropriately.

-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20100927/14677f0c/attachment.pgp>