Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм Марзулло, разработанный Китом Марзулло для его докторской диссертации в 1984 году, — это алгоритм достижения согласия, используемый для выбора источников для оценки точного времени на основе нескольких зашумленных источников времени. Усовершенствованная версия этого алгоритма, переименованная в "алгоритм пересечения", входит в состав современного протокола сетевого времени (NTP). Алгоритм Марзулло также применяется для вычисления обобщенного пересечения n прямоугольников (или, в более общем случае, n подмножеств Rn), что необходимо для ряда устойчивых методов оценки множеств.
Marzullo's algorithm, invented by Keith Marzullo for his Ph. D. dissertation in 1984, 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. 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.
Цель
Алгоритм Марзулло эффективен по времени для получения оптимального значения из набора оценок с доверительными интервалами, в случае когда фактическое значение может выходить за пределы доверительного интервала для некоторых источников. В этом случае наилучшей оценкой считается наименьший интервал, согласованный с наибольшим числом источников. Например, если у нас есть оценки 10 ± 2, 12 ± 1 и 11 ± 1, то соответствующие интервалы будут [8, 12], [11, 13] и [10, 12], которые пересекаются, образуя [11, 12] или 11,5 ± 0,5, что согласуется со всеми тремя значениями. Если же интервалы будут [8, 12], [11, 13] и [14, 15], то интервала, согласованного со всеми этими значениями, не существует, но [11, 12] согласуется с наибольшим числом источников – а именно, с двумя из них. Наконец, если интервалы будут [8, 9], [8, 12] и [10, 12], то оба интервала [8, 9] и [10, 12] согласуются с наибольшим числом источников. Эта процедура определяет интервал. Если требуется получить наилучшее значение из этого интервала, то наивный подход заключается в принятии центра интервала в качестве значения, что и было предусмотрено в оригинальном алгоритме Марзулло. Более сложный подход учитывает, что это может приводить к потере полезной информации из доверительных интервалов источников, и вероятностная модель источников может вернуть значение, отличное от центра. Следует отметить, что вычисленное значение, вероятно, лучше описывать как «оптимистичное», а не «оптимальное». Например, рассмотрим три интервала [10, 12], [11, 13] и [11,99, 13]. Алгоритм, описанный ниже, вычислит [11,99, 12] или 11,995 ± 0,005, что является очень точным значением. Если мы подозреваем, что одна из оценок может быть неверной, то как минимум две оценки должны быть правильными. При этом условии наилучшей оценкой будет [11, 13], поскольку это самый большой интервал, который всегда пересекается как минимум с двумя оценками. Алгоритм, описанный ниже, легко параметризуется максимальным числом неверных оценок.
Marzullo's algorithm is efficient in terms of time for producing an optimal value 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 consistent with the largest number of sources. 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 consistent with all three values. If instead the ranges are [8,12], [11,13] and [14,15] then there is no interval consistent with all these values but [11,12] is consistent with the largest number of sources — namely, two of them. Finally, if the ranges are [8,9], [8,12] and [10,12] then both the intervals [8,9] and [10,12] are consistent with the largest number of sources. This procedure determines an interval. If the 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, which is what was specified in the 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 probabilistic model of the sources could return a value other than the center. Note that the computed value is probably better described as "optimistic" rather than "optimal". For example, consider three intervals [10,12], [11, 13] and [11.99,13]. The algorithm described below computes [11.99, 12] or 11.995 ± 0.005 which is a very precise value. If we suspect that one of the estimates might be incorrect, then at least two of the estimates must be correct. Under this condition, the best estimate is [11,13] since this is the largest interval that always intersects at least two estimates. The algorithm described below is easily parameterized with the maximum number of incorrect estimates.
Эффективность
Алгоритм Марзулло эффективен как по объему используемой памяти, так и по времени выполнения. Асимптотический объем используемой памяти составляет O(n), где n — количество источников. При анализе асимптотической временной сложности алгоритм можно разбить на этапы: построение таблицы, ее сортировку и поиск по ней. Сортировка может быть выполнена за время O(n log n), что является доминирующей операцией по сравнению с построением таблицы и поиском, которые могут быть выполнены за линейное время. Следовательно, временная эффективность алгоритма Марзулло составляет O(n log n). После построения и сортировки таблицы обновление интервала для одного источника (при получении новой информации) возможно за линейное время. Таким образом, обновление данных для одного источника и поиск оптимального интервала могут быть выполнены за время O(n).
Marzullo's algorithm is efficient in both space and time. The asymptotic space usage is O(n), where n is the number of sources. In considering the asymptotic time requirement the algorithm can be considered to consist of building the table, sorting it and searching it. Sorting can be done in O(n log n) time, and this dominates the building and searching phases which can be performed in linear time. Therefore, the time efficiency of Marzullo's algorithm is O(n log n). 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. Therefore, updating data for one source and finding the best interval can be done in O(n) time.