Intersection algorithm


The intersection algorithm is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. It forms part of the modern Network Time Protocol. It is a modified form of Marzullo's algorithm.
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 of all the sources in the intersection. The intersection 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 ± r, the algorithm seeks to find an interval with M−f sources. The value f is referred to as the number of falsetickers, those sources which are in error. The best estimate is that which assumes the least number of falsetickers, f. The results will be considered valid if f < M/2, otherwise the algorithm will return failure instead of an interval.
The intersection algorithm begins by creating a table of tuples . For each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types −1, 0 and +1 respectively. Thus the interval c ± r results in the entries <c−r,−1>, <c,0> and <c+r,+1>. These entries are then sorted by offset.
Variables: This algorithm uses f as number of false tickers, endcount and midcount are integers. Lower and upper are values of offsets.
  2. 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 ≥ M/2.
  3. endcount=0 and midcount=0.
  4. Start at beginning of the list consider each tuple in order. endcount = endcount−type. If endcount ≥ M−f then lower = offset and goto step 3 because the lower endpoint has been found. If the type = 0 then midcount = midcount+1. Repeat with next tuple. If reach end of list then goto step 6.
  5. set endcount=0.
  6. Start from end of list and work towards lower offsets. endcount = endcount+type. If endcount ≥ M−f then upper = offset, goto step 5. If type = 0 then midcount = midcount+1. Repeat for next tuple. If reach end of list then goto step 6.
  7. if lower ≤ upper and midcount ≤ f then return interval as resulting confidence interval.
  8. f = f+1. If f ≥ M/2 then terminate and return FAILED, otherwise goto step 1.