Marzullo's algorithm
Marzullo's algorithm, invented by Keith Marzullo for his Ph.D. dissertation, 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.
Purpose
In general, Marzullo's algorithm is an algorithm, efficient in terms of time, for finding an optimal interval from a set of estimates with confidence intervals where the actual value may be outside the confidence interval for some sources. In this case the best estimate is taken to be the smallest interval consistant with the largest number of source.
If we have the estimates 10 +/- 2, 12 +/- 1 and 11 +/- 1 then these intervals are [8,12] [11,13] and [10,12] which intersect to form [11,12] or 11.5 +/- 0.5 as consistant with all the values. If the ranges were instead [8,12] [11,13] and [14,15] then there is no interval consistant with all these values but [11,12] is consistant with the largest number of sources (2). Finally, if the ranges were [8,9] [8,12] [10,12] then both the intervals [8,9] and [10,12] would be consistant with the largest number of sources.
This procedure determines an interval, if desired result is a best value from that interval then a naive approach would be to take the center of the interval as the value, this is what was specified int eh original Marzullo algorithm. A more sophisticated approach would recognize that this could be throwing away useful information from the confidence intervals of the sources and that a problistic model of the sources coudl return a value other than the center.
Method
Marzullo's algorithm begins by preparing a table of the sources, sorting it and then searching (efficiently) for the intersections of intervals.
References
- K. A. Marzullo. Maintaining the Time in a Distributed System: An Example of a Loosely-Coupled Distributed Service. Ph.D. dissertation, Stanford University, Department of Electrical Engineering, February 1984.