[ntp:questions] Number of Stratum 1 & Stratum 2 Peers

William Unruh unruh at invalid.ca
Thu Dec 4 17:36:58 UTC 2014


On 2014-12-04, brian utterback <brian.utterback at oracle.com> wrote:
>
> On 12/3/2014 5:33 PM, William Unruh wrote:
>> On 2014-12-03, Jan Ceuleers <jan.ceuleers at computer.org> wrote:
>>> On 12/03/2014 02:58 PM, Brian Utterback wrote:
>>>> I still think that it takes four to
>>>> guarantee a majority but I don't have proof of that. Someday I will
>>>> spend some time to either prove or disprove it, but alas, time is
>>>> something I don't generally have extra to spend. But you are better off
>>>> with one than two from an operational standpoint.
>>> It takes three servers *at all times* to enable clients to use majority
>>> voting. So if you want to guard against a single failure (i.e. not a
>>> single falseticker, a single server that goes offline), then you need four.
>> Offline IS a false ticker. And no, you need three. In fact to gaurd
>> against offline, you only need two. Guarding against falseticking is
>> harder than guarding against offline. Just as it is harder to guard
>> against a liar than a dead man. 
>>
>>
>
> I remain unconvinced. I believe that it takes three correct servers to
> outvote a single falseticker, meaning that if you want to be safe
> against one of your servers becoming a falseticker and still being
> accepted as the system server by a client, the client needs at least
> four servers.
>
> Remember that a "vote" is not for a single offset, it is for a single
> offset plus or minus the error, which in our case is the dispersion. Be
> definition a truechimer is a server whose range of offset-disp to
> offset+disp includes the actual time, while a falseticker is a server
> whose range does not include the actual time. Now suppose you have three
> servers, two truechimers and one falseticker, call them T1, T2 and F.
> The actual time is a bit above the T1 offset, meaning it is in the
> interval between T1off and T1off+T1disp. The actual time is also in the
> interval T2off-T2disp and T2off, which is to say that they both overlap
> with the real time but neither overlaps the other's offset.
>
> Now imagine that the falseticker has a similar overlap with T1, but on
> the interval T1off-T1disp to T1off. That interval does not include the
> real time, so F is indeed a falseticker. So, we have a completely
> symmetric situation, with T1 and F "voting" for an interval that does
> not include the real time and T1 and T2 "voting" for an interval that
> does include the real time. By what mechanism are we to presume that the
> client will choose the interval that includes the real time?
>

No. A false ticker is NOT something whose range does not overlap the true time.
the system has absolutely no way of knowing what the true time is. All
it has is the reports from the remote clocks and their dispersion. 
As I understand it, ntpd looks for "islands"-- groups of remote clocks
whose ranges overlap each other. The island with a majority of members
is by definition the island of truechimers. All others are false
tickers. Now, it could be that the majority is way off -- 400 days off
from the true time. They are still the truechimers, because the system
has no way of knowing what the true time is. 

In your example, if T1 and T2 are in one island, and F1 and F2 are in
another, what waydoes the system have of determining which is the true
time?
And in your case if T3 has exactly the same time and dispersion as T1,
how does the system decide? 

There is simply no way of deciding which will be robust against all
scenarios. It is impossible (It is basically like Arrow's theorem on voting
that no voting system can have all of the attributes one would like a
real voting system to have.)



More information about the questions mailing list