Marzullo's algorithm is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. It was invented by Keith Marzullo for his Ph.D. dissertation in 1984. A refined version of it, renamed the intersection algorithm, forms part of the modern Network Time Protocol. The algorithm is also used to compute the relaxed intersection of n boxes, or more generally n subsets of n-dimensional real space, as required by several robust set estimation methods.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Marzullo's algorithm (Wikipedia)
Sources
1. Marzullo's algorithm (Wikipedia)
Efficiency section
Therefore, the time efficiency of Marzullo's algorithm is O(n log n).
In Group: Concurrency and Distributed Systems Techniques, Lead section
is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources.
In Field: Distributed Computing, Lead section
is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.