[ntp:questions] Re: polling algorithm

David Schwartz davids at webmaster.com
Mon Sep 5 06:04:43 UTC 2005


<brian.utterback at sun.com> wrote in message 
news:1125851329.151590.93930 at g43g2000cwa.googlegroups.com...

> David Schwartz wrote:

>> "Brian Utterback" <brian.utterback at sun.removeme.com> wrote in message
>> news:431861A4.8070108 at sun.removeme.com...
>>
>> >>     Here's the simple proof. The time is 5:15. One server says:
>> >>
>> >> 5:14 plus/minus 2 minutes
>> >>
>> >>     The other says:
>> >>
>> >> 5:15 plus/minus 2 minutes
>> >>
>> >>     Now, what can the third insane clock say that will make you think
>> >> it's any time other than 5:12-5:17?
>>
>> > That's easy. How about 5:13 plus/minus 1 minute? Since you said the
>> > time is actually 5:15, this is by definition a falseticker, since
>> > the correct time is not within its interval. But the interval
>> > 5:13-5:14 overlaps all three servers, so this is where they
>> > all agree, so it must be where the correct time is, no?
>>
>>     5:13 plus/minus 2 minutes would be correct. Only one clock claimed an
>> accuracy window of one minutes. We can't base our conclusions on just one
>> clock.

> Why would plus or minus 2 minutes be correct? The confidence interval
> for a clock is a computed value based on observed data, not something
> that is "claimed".  Ah, I just re-read your postings and you said that
> the clocks provide an accuracy estimate. That's seems a bit strange.

    It doesn't matter whether the clocks provide them or not. You just have 
to define "correct" somehow, and it can't mean providing the exactly correct 
instaneous timestamp on demand. So what I did was define a clock as "valid" 
if, at any time, that clock can provide us with a small window in which the 
correct time resides. The definition of "small" is that it's an amount we 
won't be upset if our clock is off by that much.

> The process of synchronizing clocks involves determining the offset
> between your clock and "real" time, and then reducing that offset as
> closely as possible to zero. In normal operation of NTP, the plus or
> minus would represent the confidence we have that we have determined
> the offset between our clock and the server's clock, not what the
> server claims its own accuracy is. We do summate all of the confidence
> intervals up the tree to the Stratum 0 clocks, but that wouldn't apply
> in this example.

    The confidence intervals will worsen from stratum to stratum. An 
algorithm that claims a confidence interval smaller than all but one of its 
peers is broken (since it's relying on a single clock).

>>     It is possible that a naive algorithm could be mislead. However, it
>> cannot be mislead by much. Remember, part of the definition of an 
>> "accurate"
>> clock was that its confidence window was small. You've only thrown the 
>> clock
>> estimate off by that much. So you've thrown it off by a small amount.

>>     Note that the correct time is 5:15 in the example. By definition, the
>> two minutes the two clocks is off are a "small amount". So any time 
>> between
>> 5:13-5:17 would be acceptable, that is, off by only a small amount.

> If there is only one clock, I think we can all agree that there is no
> way to determine whether it is a falseticker. If there are two clocks
> that disagree \ (as you defined it, their confidence intervals do not
> overlap) then again there is no way to determine which is correct,
> where you defined correct as the actual time falls within it confidence
> interval. The question on the table is whether or not given three
> servers, two of which have overlapping confidence intervals that
> include the actual time within the overlap, and one of which has a
> confidence interval that does not overlap with the acutal time, it is
> always possible to determine which of the three servers is the
> falseticker and remove it from consideration, without resorting to
> information or algorithms that would be impractical in a real world
> network situation.

    I never said you could determine which was the falseticker and eliminate 
it. I said you could still determine the correct time and place it within a 
small interval. And you can.

> Your original claim that not only is it always possible, it is "hard to
> imagine an algorithm that wouldn't automatically recognize and fix this
> situations[sic]".

    Any algorithm that requires at least two clocks to agree to its 
conclusion will correctly determine the time in this situation. Only an 
algorithm that follows a single clock will be mislead.

> The claim of the NTP community is no, it is not
> always possible, although I believe that Leslie Lamport published an
> algorithm that requires the exchange of digital signatures that makes
> it possible, but I have no idea how that works, or even if that work is
> applicable in this thought experiment. So, barring the use of digital
> sigantures, can it be done?

    It is possible to determine the correct time, off by no more than a 
small amount. Where "small amount" was defined based upon what it meant for 
the two servers to provide correct time.

> You set up an experiment and claimed that no reasonable algorithm
> wouldn't determine the falseticker. I gave you an example server and
> implicitly a reasonable algorithm could not detect the falseticker and
> gave the wrong time.

    Your example had *NO* falseticker. Your alleged false ticker was off 
only by a small amount, which is not enough to be a falseticker. It is not a 
truechimer, because its interval did not include the correct time, but it 
was not a falseticker, because it was off by only a small amount.

> You disallowed the smaller confidence window I
> used for no reason I understand, and essentially redefined my exmaple
> to be a truechimer, while admitting that "a naive algorithm could be
> mislead."  Since I was esstentially using the same algorithm that NTP
> uses in practice (translated to these conditions) I don't think that it
> is "naive".

    It is naive to shrink your confidence interval below that of the servers 
you are relying on to provide the time unless you have a large number of 
agreeing servers.

> Not to put too fine a point on it, consider this:
>
> 1. Actual time is 5:15.
> 2. Server A has 5:13 plus or minus 3 minutes.
> 3. Server B has 5:17 plus or minus 3 minutes.
> 4. Server C has 5:21 plus or minus 3 minutes.
>
> Server A and B are true chimers. Server C is a falseticker.

    No. We have defined 3 minutes as a small amount, since we are calling A 
and B truechimers even though they only place the time within this window. 
C's window includes 5:17, which is only a small amount away from the correct 
time. C is neither a truechimer nor a falseticker.

> 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.

    DS





More information about the questions mailing list