[ntp:questions] Magice Server Numbers: 4,5,7,9

Brian Utterback brian.utterback at oracle.com
Fri Sep 16 13:06:27 UTC 2011


On 09/16/11 02:19, unruh wrote:
> On 2011-09-16, Doug Calvert <dfc-list at douglasfcalvert.net> wrote:
>> Hello,
>>  From time to time people mention that the magic number of servers is
>> 4,5,7 and nine. However I can not find a reference or explanation for
>> the magical properties. Can anyone explain the background/basis in
>> general? And specifically how is five or seven preferable to six?
> 
> Odd numbers are better than even-- cannot have a tie (well, actually it
> could) 
> It is actually 3 that is the magic number. (can outvote one false
> ticker.) 5 can outvote 2, 7 can outvote 3. With 6 three may be a tie,
> and the three good ones will not necessarily outvote three false tickers
> ( but can 2) 

I still maintain that the real reason that you need four and not just
three is that the decisions are made based on overlapping intervals, not
on exact offset numbers.

At one point, Dr. Mills said that it was a Byzantine General problem,
which of course has the formula for minimum generals vs. traitors of
"3t+1", so to detect one falseticker this would mean we would need 4
servers. However, he has since backed off from this and says that NTP is
not a true Byzantine General problem, so the formula many not apply.

What we do see now is that there apparently is no number of servers that
will always detect a single falseticker in all cases. However, for
almost all of the more esoteric cases it requires a dispersion for some
of the servers to be in a range that they would have been knocked out as
insane before the selection algorithm even gets them, so as a practical
matter, the problem mostly does not come up.

But when you consider the so-called "votes" from each server as
intervals, it is easy to see that with only 3 such "votes" a very common
situation is that if one is a false ticker, the interval it provides can
easily overlap one of the truechimer "votes" making it impossible for
NTP to decide which two "out votes" the third. While adding a fourth
server does not necessarily solve the problem (the new server might
exactly match the interval for the truechimer that has the overlap, thus
reinforcing the one server that was already known to be true) it is much
more likely to overlap the second truechimer and not the falseticker.

Unfortunately, this come up quite often, but we still seem to be dealing
with speculation on it. I keep meaning to build a graphical simulator
based on actual selection algorithm so we could get actual stats and see
what the different situations are, but alas, there are not enough hours
in a day. Maybe some day.

-- 
blu

Always code as if the guy who ends up maintaining your code will be a
violent psychopath who knows where you live. - Martin Golding
-----------------------------------------------------------------------|
Brian Utterback - Solaris RPE, Oracle Corporation.
Ph:603-262-3916, Em:brian.utterback at oracle.com



More information about the questions mailing list