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

> 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