[ntp:questions] outlyer / falseticker

Brian Utterback brian.utterback at oracle.com
Thu Mar 7 13:43:07 UTC 2013


Okay, it can be a little obtuse, especially if you don't know the 
references. The two specific references that are being used here are the 
reality television show "Survivor" and "The Byzantine Generals Problem", 
an algorithm for detecting misbehaving parts of a system, in this case 
an NTP server.

Comments inline:

On 3/7/2013 7:22 AM, folkert wrote:
> Ok.
>
> While reading through the source, I encountered a lot of unusual
> comments:
>           * Initially, we populate the island with all the rifraff peers
>
> rifraff?

Riff Raff: disreputable person.  This is saying initially use all of the 
candidate servers, no matter how good or bad they appear.

>
>           * that happen to be lying around. Those with seriously
>           * defective clocks are immediately booted off the island. Then,
>           * the falsetickers are culled and put to sea. The truechimers
>
> cullend and put to sea?

Seriously defective means not selectable because either the server is 
not in sync or the root sync distance is too large, or it doesn't meet 
administrative criteria (stratum too low, too high, configured noselect, 
or makes a sync loop).  The algorithm takes what is left and looks for 
false tickers. This is a little tricky to describe in English, but it 
essentially looks at the offset and error bars from all the remaining 
servers and determines a consensus interval in which the true offset 
lies. A falseticker is any server with an offset that does not lie 
within that interval. If a server is tagged as a falseticker, it is 
removed from further consideration, which is the what "culled and put to 
sea" means in this case.

>
>           * remaining are subject to repeated rounds where the most
>           * unpopular at each round is kicked off. When the population
>           * has dwindled to sys_minclock, the survivors split a million
>           * bucks and collectively crank the chimes.
>
> split a million bucks?

This is where the Byzantine General solution comes into play. We 
repeatedly try to narrow the consensus interval of the remaining servers 
until we get the smallest possible interval. All servers with offsets in 
the smallest interval are candidates for selection. It is possible that 
there is no consensus and it is not possible choose a server that has 
any better likelihood of being correct than any other and they do not 
agree, which leads us to the next comment.
>
>           * candidates, the Albanians have won the Byzantine wars and
>           * correct synchronization is not possible.
>
> byzantine wars?

The Byzantine Generals Problem is based on an allegory with the problems 
the generals in the Byzantine empire had fighting the Albanians. This 
comment is saying if there is no consensus among the Byzantine generals, 
then they cannot act and Albania wins the war. That is, no servers are 
selectable.

After that there is more culling of the rest, using jitter and distance 
to find the best quality of time of the remaining servers. And then the 
weighting algorithm may come into play to get the final offset used. 
Servers culled at this point at marked as "Excess", since they had good 
time, but the culling continues until there are only sys_minclock 
servers left.

Hope that make it more clear.
Brian.


More information about the questions mailing list