{"history":[],"article":{"id":"2d95cacf-bd7a-481d-a594-edfecfd31055","title":"Intersection algorithm","slug":"intersection-algorithm","content":":::summary\n:::\n\n# \nThe **intersection algorithm** is an agreement algorithm used to select sources for estimating accurate time from a number of [noisy](https://bliptext.com/articles/noise) time sources.\nIt forms part of the modern [Network Time Protocol](https://bliptext.com/articles/network-time-protocol).\nIt is a modified form of [Marzullo's algorithm](https://bliptext.com/articles/marzullo-s-algorithm).\nWhile 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.\nThe intersection algorithm returns an interval that includes that returned by Marzullo's algorithm but may be larger since it will include the center points.\nThis larger interval allows using additional statistical data to select a point within the interval, reducing the [jitter](https://bliptext.com/articles/jitter) in repeated execution.\n\n# Method\nGiven M intervals of the form c ± r (which means [c−r,c+r]), the algorithm seeks to find an interval with M−f sources.\nThe value f is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the [confidence band](https://bliptext.com/articles/confidence-band)).\nThe best estimate is that which assumes the fewest falsetickers, f.\nThe results will be considered valid if f < M/2, otherwise the algorithm will return failure instead of an interval.\nThe intersection algorithm begins by creating a table of tuples .\nFor each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types −1, 0 and +1 respectively.\nThus the interval c ± r results in the entries , and .\nThese entries are then sorted by offset.\nVariables: This algorithm uses f as number of false tickers, endcount and midcount are integers.\nLower and upper are values of offsets.\n

[initialize best f] Start with f=0, assuming all input intervals are valid.\nEach time no interval is found f will be incremented until either an interval is found or f ≥ M/2.

[initialize] endcount=0 and midcount=0.

[find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order.\nendcount = endcount−type.\nIf endcount ≥ M−f then lower = offset and goto step 3 because the (possible) lower endpoint has been found.\nIf the type = 0 then midcount = midcount+1, Repeat with next tuple.\nIf reach end of list then goto step 6.

[tentative lower endpoint found, initialize to find upper endpoint] set endcount=0.\n

[determine number of midpoints] Start from end of list and work towards lower offsets.\nendcount = endcount+type.\nIf endcount ≥ M−f then upper = offset, goto step 5.\nIf type = 0 then midcount = midcount+1, Repeat for next tuple.\nIf reach end of list then goto step 6.

if lower ≤ upper and midcount ≤ f then return interval [lowerendpoint, upperendpoint] as resulting confidence interval.

[increment number of falsetickers] f = f+1.\nIf f ≥ M/2 then terminate and return FAILED, otherwise goto step 1.

\n","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:14:31.848Z","updated_at":"2025-01-25T21:14:31.848Z","search_vector":"'algorithm':2 'intersect':1","search_content":" \n \n\n# \nThe **intersection algorithm** is an agreement algorithm used to select sources for estimating accurate time from a number of [noisy](https://bliptext.com/articles/noise) time sources.\nIt forms part of the modern [Network Time Protocol](https://bliptext.com/articles/network-time-protocol).\nIt is a modified form of [Marzullo's algorithm](https://bliptext.com/articles/marzullo-s-algorithm).\nWhile 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.\nThe intersection algorithm returns an interval that includes that returned by Marzullo's algorithm but may be larger since it will include the center points.\nThis larger interval allows using additional statistical data to select a point within the interval, reducing the [jitter](https://bliptext.com/articles/jitter) in repeated execution.\n\n# Method\nGiven M intervals of the form c ± r (which means [c−r,c+r]), the algorithm seeks to find an interval with M−f sources.\nThe value f is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the [confidence band](https://bliptext.com/articles/confidence-band)).\nThe best estimate is that which assumes the fewest falsetickers, f.\nThe results will be considered valid if f .\nFor each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types −1, 0 and +1 respectively.\nThus the interval c ± r results in the entries , and .\nThese entries are then sorted by offset.\nVariables: This algorithm uses f as number of false tickers, endcount and midcount are integers.\nLower and upper are values of offsets.\n [initialize best f] Start with f=0, assuming all input intervals are valid.\nEach time no interval is found f will be incremented until either an interval is found or f ≥ M/2. \n [initialize] endcount=0 and midcount=0. \n [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order.\nendcount = endcount−type.\nIf endcount ≥ M−f then lower = offset and goto step 3 because the (possible) lower endpoint has been found.\nIf the type = 0 then midcount = midcount+1, Repeat with next tuple.\nIf reach end of list then goto step 6. \n [tentative lower endpoint found, initialize to find upper endpoint] set endcount=0.\n \n [determine number of midpoints] Start from end of list and work towards lower offsets.\nendcount = endcount+type.\nIf endcount ≥ M−f then upper = offset, goto step 5.\nIf type = 0 then midcount = midcount+1, Repeat for next tuple.\nIf reach end of list then goto step 6. \n if lower ≤ upper and midcount ≤ f then return interval [lowerendpoint, upperendpoint] as resulting confidence interval. \n [increment number of falsetickers] f = f+1.\nIf f ≥ M/2 then terminate and return FAILED, otherwise goto step 1. \n ","revisionCount":0},"hasMore":false,"nextCursor":null}

History