Intersection algorithm

Last updated

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. [1] [2]

While Marzullo's algorithm will return the smallest interval consistent with the largest number of sources, the [1] 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 fewest 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 <offset, type>. 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.

  1. [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.
  2. [initialize] endcount=0 and midcount=0.
  3. [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.
  4. [tentative lower endpoint found, initialize to find upper endpoint] set endcount=0.
  5. [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.
  6. if lower ≤ upper and midcount ≤ f then return interval [lowerendpoint, upperendpoint] as resulting confidence interval.
  7. [increment number of falsetickers] f = f+1. If f ≥ M/2 then terminate and return FAILED, otherwise goto step 1.

Related Research Articles

The Session Description Protocol (SDP) is a format for describing multimedia communication sessions for the purposes of announcement and invitation. Its predominant use is in support of streaming media applications, such as voice over IP (VoIP) and video conferencing. SDP does not deliver any media streams itself but is used between endpoints for negotiation of network metrics, media types, and other associated properties. The set of properties and parameters is called a session profile.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers x satisfying 0 ≤ x ≤ 1 is an interval which contains 0, 1, and all numbers in between. Other examples of intervals are the set of numbers such that 0 < x < 1, the set of all real numbers , the set of nonnegative real numbers, the set of positive real numbers, the empty set, and any singleton.

<span class="mw-page-title-main">Network Time Protocol</span> Standard protocol for synchronizing time across devices

The Network Time Protocol (NTP) is a networking protocol for clock synchronization between computer systems over packet-switched, variable-latency data networks. In operation since before 1985, NTP is one of the oldest Internet protocols in current use. NTP was designed by David L. Mills of the University of Delaware.

<span class="mw-page-title-main">Numerical integration</span> Family of algorithms for finding the definite integral of a function

In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations. This article focuses on calculation of definite integrals.

Collision detection is the computational problem of detecting the intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing fields, primarily in computer graphics, computer games, computer simulations, robotics and computational physics. Collision detection algorithms can be divided into operating on 2D and 3D objects.

<span class="mw-page-title-main">Riemann sum</span> Approximation technique in integral calculus

In mathematics, a Riemann sum is a certain kind of approximation of an integral by a finite sum. It is named after nineteenth century German mathematician Bernhard Riemann. One very common application is approximating the area of functions or lines on a graph, but also the length of curves and other approximations.

Branch and bound is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

<span class="mw-page-title-main">Bisection method</span> Algorithm for finding a zero of a function

In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain a root. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods. The method is also called the interval halving method, the binary search method, or the dichotomy method.

In mathematics, the regula falsi, method of false position, or false position method is a very old method for solving an equation with one unknown; this method, in modified form, is still in use. In simple terms, the method is the trial and error technique of using test ("false") values for the variable and then adjusting the test value according to the outcome. This is sometimes also referred to as "guess and check". Versions of the method predate the advent of algebra and the use of equations.

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 "intersection algorithm", forms part of the modern Network Time Protocol. Marzullo's algorithm is also used to compute the relaxed intersection of n boxes, as required by several robust set estimation methods.

<span class="mw-page-title-main">Parallax mapping</span>

Parallax mapping is an enhancement of the bump mapping or normal mapping techniques applied to textures in 3D rendering applications such as video games. To the end user, this means that textures such as stone walls will have more apparent depth and thus greater realism with less of an influence on the performance of the simulation. Parallax mapping was introduced by Tomomichi Kaneko et al., in 2001.

<span class="mw-page-title-main">Nested intervals</span>

In mathematics, a sequence of nested intervals can be intuitively understood as an ordered collection of intervals on the real number line with natural numbers as an index. In order for a sequence of intervals to be considered nested intervals, two conditions have to be met:

  1. Every interval in the sequence is contained in the previous one.
  2. The length of the intervals get arbitrarily small.

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings, the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .

<span class="mw-page-title-main">Line segment</span> Part of a line that is bounded by two distinct end points; line with two endpoints

In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints. In geometry, a line segment is often denoted using a line above the symbols for the two endpoints.

In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.

The relaxed intersection of m sets corresponds to the classical intersection between sets except that it is allowed to relax few sets in order to avoid an empty intersection. This notion can be used to solve Constraints Satisfaction Problems that are inconsistent by relaxing a small number of constraints. When a bounded-error approach is considered for parameter estimation, the relaxed intersection makes it possible to be robust with respect to some outliers.

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

Q# is a domain-specific programming language used for expressing quantum algorithms. It was initially released to the public by Microsoft as part of the Quantum Development Kit.

In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map with key type , comparison function on and value type , the augmented value is defined based on two functions: a base function and a combine function , where is the type of the augmented value. The base function converts a single entry in to an augmented value, and the combine function combines multiple augmented values. The combine function is required to be associative and have an identity . We extend the definition of the associative function as follows:

References

  1. 1 2 Mills, D. (2013). "RFC 1305 - Network Time Protocol (Version 3) Specification, Implementation and Analysis". tools.ietf.org. doi:10.17487/RFC1305 . Retrieved October 6, 2013. Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989.
  2. ↑ Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.