Re: WG ACTION: 2 weeks to discuss [LL62] Do not space probes randomly

I agree with Philip's reasoning - the subsequent randomization addresses the
(admittedly small, assuming good random number generators) problem that two
hosts might pick an initial delay within a collision window of each other.
If there is no randomization of subsequent probes, there is no point in
specifying multiple probes.

- Ralph

At 09:34 AM 5/7/2004 +0000, Philip Nye wrote:
> > From: "Stuart Cheshire" <[email protected]>
> >
> > ...but the biggest problem may be this:
> >
> > The sum of random variables is LESS random than the individual variables.
> >
> > Ask any statistician, or do a Google search for "central limit theorem"
> > or "strong law of large numbers".
> >
> > Here's a simple example that should be familiar to everyone:
> >
> > If you throw one die, the numbers 1,2,3,4,5,6 are all equally likely.
> >
> > If you throw two dice, and add up the results, then 7 is the most likely
> > outcome. You are SIX TIMES more likely to get 7 than either 2 or 12.
>
>Stuart,
>
>This is a completely spurious statistical argument I'm afraid. If you want 
>to use the dice example - here is the scenario:
>
>You an I both generate a series of 4 numbers. The first value is generated 
>by throwing a single die.
>
>case A. Each subsequent value is generated by adding 4, 3 and 4 
>respectively to the preceeding value.
>
>case B. Each subsequent value is generated by throwing the die again and 
>adding that value to the preceeding value.
>
>Now the probability that you are talking about is that you and I agree on 
>AT LEAST ONE value in our series which does increase in case B. It is 1/6 
>for A and approximately 0.52 for B.
>
>However that is irrelevant, the chance we need to avoid is that you and I 
>both agree on ALL FOUR values in our series. For A this probability is 1/6 
>while for B it is 1/(6^4) = 1/1296.
>
>Returning to the computer algorithm, given the fact that in many 
>implementations a "random" delay is likely to be quantised to the inherent 
>tick frequency of the operating system, then the probability of an initial 
>delay in the range 0..1 second being the same for two hosts is not very 
>low (1/100 for a typical OS and as big as 1/20 for some). Making 
>subsequent delays also random drastically increases the chances that at 
>least some of the probes will not clash.
>
>What is the reason for sending four probes? In the case of only the 
>initial delay being randomised, the extra ones merely guard against the 
>possibility that probes may be dropped or lost. In the case of consecutive 
>random delays this still applies but they have the added benefit of 
>reducing the chances of all probes being lost because of timing clashes.
>
>In conclusion. I agree with Christian that the initial wait should be in 
>the range 0..(PROBE_MAX - PROBE_MIN) which is different from the current 
>draft. I also agree with him that the subsequent delays should be 
>randomised exactly as in the current draft.
>
>Philip