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

David L. Mills mills at udel.edu
Sun Mar 20 04:08:03 UTC 2005


We are all reading too much in this discussion, including me. The NTP 
selection algorithm is not a Byzantine agreement algorithm; it is a 
majority subset algorithm. If the correctness intervals of two servers 
overlap, but not with a third, a majority subset has been found. 
However, operating with four client/servers in peer mode is a different 
story and would in general require four peers. In this mode all 
truechimers would have to agree on who the falseticker is.

Even with four peers a bulletproof agreement would be possible only if 
all peers could see the timestamps of all other peers. On several 
occasions I have proposed a new mode called NTP distributed mode. Each 
peer woulr broadcast its timestmaps and those received from other peers. 
The timestamps could be contained in extension fields. I challenge our 
weekend warriors to carry out such an adventure.

If I can get das Buch out the door and survive the standards effort, I 
might even launch that adventure myself, but I would rather somebody 
beat me to it.


David Schwartz wrote:

> "Richard B. Gilbert" <rgilbert88 at comcast.net> wrote in message 
> news:vP6dndrj_8jgOaHfRVn-ug at comcast.com...
>>Aren't you assuming that the "*you*" already knows what time it is?
>     No. The Byzantine Generals algorithm does not assume that any of the 
> lieutenants already know the answer. In the case of NTP, the General is UTC 
> and the Lieutenants are the time servers.
>>The objective of running NTP is to find out what time it is!
>     Right.
>>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.
>     And if you use three, of which two are working properly, you will too. 
> Those two will agree. The third will either agree or disagree. If agrees, no 
> harm. If disagrees, he's outvoted.
>     DS

More information about the questions mailing list