On 09/16/11 02:19, unruh wrote: > On 2011-09-16, Doug Calvert <[email protected]> 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:[email protected] _______________________________________________ questions mailing list [email protected] http://lists.ntp.org/listinfo/questions
