Intersection algorithm: Difference between revisions

Revision as of 18:23, 22 September 2019

Revision as of 16:29, 16 October 2019

Line 1:

{{short description|Algorithm for selecting the best sources for time estimation}}

The '''intersection algorithm''' is an [[agreement algorithm]] used to select sources for estimating accurate time from a number of [[noise|noisy]] time sources, it forms part of the modern [[Network Time Protocol]]. It is a modified form of [[Marzullo's algorithm]].<ref>{{cite web |url= http://tools.ietf.org/html/rfc1305#ref-DEC89 |title=RFC 1305 - Network Time Protocol (Version 3) Specification, Implementation and Analysis |first= |last= |work=tools.ietf.org |year=2013 |quote=Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989. |accessdate=October 6, 2013}}</ref><ref>Digital Time Service Functional Specification Version T.1.0.5. Digital

Equipment Corporation, 1989.</ref>

While Marzullo's algorithm will return the smallest interval consistent with the largest number of sources, the returned interval does not necessarily include the center point (calculated offset) of all the sources in the intersection. The Intersectionintersection algorithm returns an interval that includes that returned by Marzullo's algorithm but may be larger since it will include the center points. This larger interval allows using additional statistical data to select a point within the interval, reducing the [[jitter]] in repeated execution.

==Method==

Given ''M'' intervals of the form ''c''&nbsp;±&nbsp;''r'' (which means [''c''&minus;''r'',''c''+''r'']), the algorithm seeks to find an interval with ''M''&minus;''f'' sources. The value ''f'' is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the [[confidence band]]). The best estimate is that which assumes the least number of falsetickers, ''f''. The results will be considered valid if ''f''&nbsp;<&nbsp;''M''/2, otherwise the algorithm will return failure instead of an interval.

The intersection algorithm begins by creating a table of tuples <offset,type>. For each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types &minus;1, 0 and +1 respectively. Thus the interval ''c''&nbsp;±&nbsp;''r'' results in the entries <''c''&minus;''r'',&minus;1>, <''c'',0> and <''c''+''r'',+1>. These entries are then sorted by offset.