Miroslav,
Nowhere in the documentation produced by me is the statement that the
minimum number of servers to reliably find the truechimers is four.
There might have been some confusion in the past, in particular with
reference to Lamport's paper, which describes an algorithm much more
complicated and unsuitable for practical use. In that paper, four
Byzantine generals are necessary to detect a traitor, but only three if
digital signatures are available. The NTP algorithm, derived in part
from Keith Marzullo's dissertation, is not that algorithm.
The NTP algorithm is described on the page you cite. A constructive
proof, elaborated in my book, is simple and based on the intersection
properties of correctness intervals, which are loosely defined as the
interval equal to the roundtrip delay with the center point as the
maximum likelihood estimate of the server offset. If there are two
servers and their correctness intervals overlap, both are truechimers.
If the intervals do not overpap, no decision is possible. If there are
three servers and the intersection of two intervals is nonempty, both
are truechimers and the third is a falseticker. If no two intervals
intersect, no decision is possible.
So, it is incomplete to specify a minimum number of servers. The only
valid statement is on the page "The intersection interval is the
smallest interval containing points from the largest number of
correctness intervals." If the intersection interval contains more than
half the total number of servers; those servers are truechimers and the
others are falsetickers.
Dave
Miroslav Lichvar wrote:
Hi,
I'm wondering about the section 5.3.3 on the ntp support web
http://support.ntp.org/bin/view/Support/SelectingOffsiteNTPServers#Section_5.3.3.
It says and explains that minimum number of servers to detect one
falseticker is four, is that really correct? I understand that four is
better for reliability, but from the algorithm description
(http://www.eecis.udel.edu/~mills/ntp/html/select.html) and my tests
with a simulated falseticker it seems that three is enough.
Also, while running with two servers might be the worst configuration
for ntpd, it still could be prefered over the configuration with only
one server by users who would rather have two sources marked as
falsetickers and know a problem needs to be fixed than unknowingly
follow a bad truechimer.
Is it possible to reword that section?
Thanks,
_______________________________________________
questions mailing list
questions@lists.ntp.org
http://lists.ntp.org/listinfo/questions
