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 (calculated offset) 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" (which means ["c"−"r","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 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" < "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.

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" ≥ "m"/2.

1) [initialize] "endcount"=0 and "midcount"=0.

2) [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. "endcount" = "endcount"−"type". If "endcount" ≥ "m"−"f" then "lower" = "offset" and goto step 3 because the (possible) 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.

3) [tentative lower endpoint found, initialize to find upper endpoint] set "endcount"=0.

4) [determine number of midpoints] 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.

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

6) [increment number of falsetickers] "f" = "f"+1. If "f" ≥ "m"/2 then terminate and return FAILED, otherwise goto step 1.

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

Intersection number (graph theory) — In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover… … Wikipedia
Covariance intersection — is an algorithm for combining two or more estimates of state variables in a Kalman filter when the correlation between them is unknown.[1][2][3] Specification Items of information a and b are known and are to be fused into information item c. We… … Wikipedia
Marzullo's algorithm — Marzullo s algorithm, invented by Keith Marzullo for his Ph.D. dissertation in 1984, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. A refined version of it, renamed the… … Wikipedia
Matroid intersection — In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection… … Wikipedia
Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance … Wikipedia
Cohen–Sutherland algorithm — In computer graphics, the Cohen–Sutherland algorithm (named after Michael F. Cohen and Ivan Sutherland) is a line clipping algorithm. The algorithm divides a 2D space into 9 regions, of which only the middle part (viewport) is visible. In 1967,… … Wikipedia
Line segment intersection — In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross.Naive algorithms examine each pair of segments, but this is highly … Wikipedia
Sweep line algorithm — In computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. It is one of the key techniques in computational… … Wikipedia
Difference-map algorithm — Iterations 0, 100, 200, 300 and 400 in the difference map reconstruction of a grayscale image from its Fourier transform modulus The difference map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta… … Wikipedia
Difference map algorithm — The difference map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical… … Wikipedia

Academic Dictionaries and Encyclopedias

Intersection algorithm

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Intersection algorithm

Look at other dictionaries:

Share the article and excerpts

Direct link