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 Space Complexity 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).
Article text
Therefore, the time efficiency of Marzullo's algorithm is O(n log n).
Article text, space complexity
The asymptotic space usage is O(n), where n is the number of sources.
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.