Intersection algorithm: Difference between revisions

Revision as of 04:55, 14 March 2021

Latest revision as of 18:03, 29 March 2025

(7 intermediate revisions by 7 users not shown)

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 name=":0">{{cite webjournal |url= http://tools.ietf.org/html/rfc1305#ref-DEC89 |title=RFC 1305 - Network Time Protocol (Version 3) Specification, Implementation and Analysis |first= |last= |workwebsite=tools.ietf.org |year=2013 |doi=10.17487/RFC1305 |quote=Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989. |accessdate=October 6, 2013|last1=Mills |first1=D. |doi-access=free }}</ref><ref>Digital Time Service Functional Specification Version T.1.0.5. Digital

Equipment Corporation, 1989.</ref>

Line 13:

Variables: This algorithm uses ''f'' as number of false tickers, ''endcount'' and ''midcount'' are integers. ''Lower'' and ''upper'' are values of offsets.

<ol start="0">

# <li> value="0">[initialize best f] Start with ''f''=0, assuming all input intervals are valid. Each time no interval is found f will be incremented until either an interval is found or ''f''&nbsp;≥&nbsp;''M''/2.</li>

#<li> [initialize] ''endcount''=0 and ''midcount''=0.</li>

#<li> [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. ''endcount''&nbsp;=&nbsp;''endcount''&minus;''type''. If ''endcount''&nbsp;≥&nbsp;''M''&minus;''f'' then ''lower''&nbsp;=&nbsp;''offset'' and goto step 3 because the (possible) lower endpoint has been found. If the ''type''&nbsp;=&nbsp;0 then ''midcount''&nbsp;=&nbsp;''midcount''+1. Repeat with next tuple. If reach end of list then goto step 6.</li>

#<li> [tentative lower endpoint found, initialize to find upper endpoint] set ''endcount''=0. </li>

#<li> [determine number of midpoints] Start from end of list and work towards lower offsets. ''endcount''&nbsp;=&nbsp;''endcount''+''type''. If ''endcount''&nbsp;≥&nbsp;''M''&minus;''f'' then ''upper''&nbsp;=&nbsp;''offset'', goto step 5. If ''type''&nbsp;=&nbsp;0 then ''midcount''&nbsp;=&nbsp;''midcount''+1. Repeat for next tuple. If reach end of list then goto step 6.</li>

# if ''lower''&nbsp;≤&nbsp;''upper'' and ''midcount''&nbsp;≤&nbsp;''f'' then return interval [''lowerendpoint'', ''upperendpoint''] as resulting confidence interval.

#[increment<li> number of falsetickers]if ''flower''&nbsp;=≤&nbsp;''fupper''+1. Ifand ''fmidcount''&nbsp;≥≤&nbsp;''Mf''/2 then terminate and return FAILEDinterval [''lowerendpoint'', otherwise''upperendpoint''] gotoas stepresulting 1confidence interval.</li>

<li>[increment number of falsetickers] ''f''&nbsp;=&nbsp;''f''+1. If ''f''&nbsp;≥&nbsp;''M''/2 then terminate and return FAILED, otherwise goto step 1.</li>

</ol>

==References ==