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

David L. Mills mills at udel.edu
Sun Mar 20 03:42:58 UTC 2005


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