David L. Mills wrote:
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.
I.e. Byzantine generals not only lie, the also lie about _who_ they are,
spoofing messages from other generals. In NTP this would mean a
falsticker which also sends out packets pretending to be responses from
other servers, something which is effectively impossible unless they are
based on the same (broadcast) network and can sniff incoming requests
and/or poison the ARP tables to commandeer the other server's IP address.
Your digital signatures make such lies impossible.
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.
I think Miroslav showed an ascii art example for when three servers
might not be enough:
Two servers which don't overlap, and a third which overlaps (partly)
both of them:
<----> <----> server A and B
<---> server C
In this particular situation C must be a survivor, but since it overlaps
both A and B with an identical amount, there is no way to determine if
(A^C) or (B^C) is the best interval to pick.
I guess the key here is that this situation is impossible unless at
least one of the servers are lying (falseticker).
You could even extend this to four servers, where server D is identical
to server C, and it would be equally hard to determine if A or B was the
falseticker, right?
Fortunately, NTP timestamps have enough resolution to make the
likelyhood of multiple perfectly positioned confidence intervals
extremely unlikely, and if it does happen in a particular poll cycle,
then NTPD will happily coast on until the next poll. :-)
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
_______________________________________________
questions mailing list
questions@lists.ntp.org
http://lists.ntp.org/listinfo/questions
