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" wrote in message
>> news:d1hqk9$861$1@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. |