[ntp:questions] NTP over redundant peer links, undetected loops

Terje Mathisen "terje.mathisen at tmsw.no" at ntp.org
Sun Feb 15 21:55:57 UTC 2009

Joseph Gwinn wrote:
>> It depends on the size of the network. The chances of a duplicate
>> 32-bit number on a network including 65000 hosts is about 40%. The NTP
>> Pool network, which comprises at least 10^6 hosts, for example, would
>> have collision probability very close to 1.
> How did you compute that?  Given that 2^32= ~4*10^9, it's hard to see 
> how 10^6 hosts spread at random in a 10^9 codespace could achieve 100% 
> collision probability.

The Birthday Paradox. Google it!

As soon as you have approx sqrt(N) samples out of universe of N values, 
the chance of at least one collision breaks 50%.

As soon as you get significantly past that sqrt(N) number, i.e. 64K IP 
addresses, you pass that 50% chance.

With 1e6 random 32-bit numbers the odds are so close to 100% as makes no 
difference at all.

- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

More information about the questions mailing list