Marzullo's algorithm

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 (or more generally n subsets of Rn), as required by several robust set estimation methods.

In this case the best estimate is taken to be the smallest interval consistent with the largest number of sources.

Marzullo's algorithm begins by preparing a table of the sources, sorting it and then searching (efficiently) for the intersections of intervals.

Once the table has been built and sorted it is possible to update the interval for one source (when new information is received) in linear time.