David L. Mills wrote:
> 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.
>
Dave,
I was assuming that we were discussing the case of three servers and a
client! If we are discussing the case of four peers DS is, of course,
correct. Is it not also the case that if you are peering with three
other servers, you are at the same stratum as they are and must,
therefore, have an independent time source at a stratum one less than
your own and "know what time it is"? |