[ntp:questions] Re: polling algorithm

Terje Mathisen terje.mathisen at hda.hydro.com
Mon Sep 5 06:45:16 UTC 2005


David Schwartz wrote:
> <brian.utterback at sun.com> wrote in message 
>>We can look
>>at the intervals and determine that there is at least one falseticker
>>(in practice, the real problem is the stronger case of 0 or 1
>>falseticker, but in this example we can easily tell that falsetickers
>>are >= 1 and we are only considering the case of falsetickers <= 1, so
>>there is exactly one falseticker) So how do you tell which is the
>>falseticker if you didn't already know? I know, in this case, you can
>>determine that Server B is *not* the falseticker, so you could use that
>>server, but that isn't what I am asking.
> 
> 
>     In this case, the windows are:
> 
> A) 5:10 to 5:16
> B) 5:14 to 5:20
> C) 5:18 to 5:24
> 
>     If we aren't going to be mislead by a single clock, we pick only that 
> part of the windows that two servers agree on. We get 5:14-5:18, which 
> includes the correct time.

Brian (and David), thanks for finally making me really understand why
NTP specifies four instead of three servers!

David, your conclusion above is wrong, because there are two disjunct
intervals where two servers agree that the correct time could be:

A|B = 5:14 to 5:16
B|C = 5:18 to 5:20

With no other sources of correct time (i.e. a fourth server), there is
no way to determine if the first or the second interval is correct. I.e.
it is probable that B isn't a falseticker since it is the median choice,
but there is no way to select a single time window as better than all
others.

You could argue that the best possible choice in a situation like the
one above would indeed be to select the single server that is a member
of the largest number of possible clock intervals, but as long as the
clock selection algorithm requires a plurality to agree, this doesn't work.

Terje
-- 
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"




More information about the questions mailing list