Marzullo algorithm

"There was considerable discussion during 1989 about the newly announced Digital Time Synchronization Service (DTSS) [23], which was adopted for the Enterprise network. The DTSS and NTP communities had much the same goals, but somewhat different strategies for achieving them. One problem with DTSS, as viewed by the NTP community, was a possibly serious loss of accuracy, since the DTSS design did not discipline the clock frequency. The problem with the NTP design, as viewed from the DTSS community, was the lack of formal correctness principles in the design process. A key component in the DTSS design upon which the correctness principles were based was an agreement algorithm invented by Keith Marzullo in his dissertation.

In the finest Internet tradition of stealing good ideas, the Marzullo algorithm was integrated with the existing suite of NTP mitigation algorithms, including the filtering, clustering and combining algorithms, which the DTSS design lacked. However, the Marzullo algorithm in its original form produced excessive jitter and seriously degraded timekeeping quality over typical Internet paths. The algorithm, now called the intersection algorithm, was modified to avoid this problem. The resulting suite of algorithms has survived substantially intact to the present day, although many modifications and improvements have been made over the years."

--David Mills, "Confessions of an Internet Timekeeper"