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

Hal Murray hal-usenet at ip-64-139-1-69.sjc.megapath.net
Mon Feb 16 01:11:14 UTC 2009

>> 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.

That assumes all machines are talking to all others.  It the pool
context, we have nowhere near that much connectivity.

With a million machines, the birthday game would have 1M*1M/2
connections.  ntp/pool has 1M*3 connections.  They differ
by a factor of ballpark 100K.

These are my opinions, not necessarily my employer's.  I hate spam.

More information about the questions mailing list