[ntp:questions] Re: Sufficient # servers to sync to

John Sasso jsassojr at nycap.rr.com
Wed Mar 23 01:59:25 UTC 2005


David,

Am I correct in my interpretation of your posts that it is sufficient for an
NTP client (not a peering server, but purely an NTP client that nobody syncs
with and that does not peer with anyone), having it sync off of a minimum of
3 NTP servers is sufficient?  This way, if 1 out of the 3 was a falseticker,
the 2 truechimers would essentially "override" (i.e. prove out-of-sync) the
falseticker.

To everyone who has posted in this thread -
Thank-you!  This has been a healthy discussion of the topic :-)

--john

"David L. Mills" <mills at udel.edu> wrote in message
news:d1irk2$fqa$1 at dewey.udel.edu...
> Richard,
>
> You cite three servers and "you" as client. By assumption "you" are an
> observer and do not advise the servers. If the three servers and "you"
> were peers rather than servers and client, that would satisfy the 3n + 1
> traitor problem.
>
> The original Byzantine agreement algorithm given in Lamport's paper
> required a horrific number of exchanges and relays. However, the NTP
> selection algorithm is not based on that algorithm; it is based on an
> algorithm suggested in Marzullo's dissertation. but modified for better
> accuracy. In Marzullo's words, the algorithm finds the smallest
> intersection containing points from correct clocks, so UTC must be
> somewhere in the intersection. The NTP modifications expect UTC at the
> midpoint of each intersecting interval.
>
> Dave
>
> Richard B. Gilbert wrote:
> > David Schwartz wrote:
> >
> >> "David L. Mills" <mills at udel.edu> wrote in message
> >> news:d1hqk9$861$1 at dewey.udel.edu...
> >>
> >>
> >>
> >>> It's not true for three servers. Assuming one is falseticker, the
> >>> other two cannot from a majority clique in the voting process. You
> >>> need at least three alleged truechimers for that. I hesitate to cite
> >>> Leslie Lamport, the source of the Byzantine Generals problem, on
> >>> which this algorithm is based, but the paper is among the citations
> >>> at www.eecis.udel.edu/~mills/biblio.html.
> >>>
> >>
> >>
> >>    I hate to say this, and it's quite possible I'm wrong, but it seems
> >> to me that this is based on an erroneous understanding of the
> >> Byzantine Generals problem and its solution. If you have three
> >> servers, this is analogous to the Byzantine Generals problems with
> >> *four* entities, the three servers you have, and *you*. With four
> >> entities, each entity has three others to look at. If two are correct,
> >> they can outvote the third.
> >>
> >>    DS
> >>
> >>
> >>
> >>
> > Aren't you assuming that the "*you*" already knows what time it is?
> > The objective of running NTP is to find out what time it is!
> >
> > It is very useful to start up with a more or less correct estimate of
> > the correct time but it is by no means required.   If you use four
> > servers, of which at least three are working properly, you will
> > eventually get to the correct time.





More information about the questions mailing list