[ntp:questions] outlyer / falseticker
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.
On 3/7/2013 7:22 AM, folkert wrote:
> While reading through the source, I encountered a lot of unusual
> * Initially, we populate the island with all the rifraff peers
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
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
Hope that make it more clear.
More information about the questions