Алгоритм Марзулло — это алгоритм согласования данных, использующийся для выбора более точных источников для оценки точного времени из ряда источников времени, разной степени точности и усреднения времени, полученными от разных NTP-серверов. Переработанная версия этого алгоритма, названная «алгоритмом пересечений», является частью сетевого протокола для синхронизации времени (NTP).
Алгоритм Марзулло эффективен (в терминах времени) для получения оптимального значения из множества оценок с их доверительными интервалами. Важно, что для некоторых источников оптимальное значение может лежать вне доверительного интервала. Наилучшей оценкой следует считать наименьший интервал, соответствующий наибольшему числу источников.
Предположим, что мы имеем следующие оценки: 10 ± 2, 12 ± 1 и 11 ± 1 в интервалах [8,12], [11,13] и [10,12]. Их пересечением будет интервал [11,12] или точка 11.5 ± 0.5, соответствующая всем трём источникам.
Алгоритм Марзулло, пример
Распишем алгоритм по шагам:
Построить таблицу кортежей. Каждый кортеж является парой: смещение и тип. Смещение содержит значение времени для начала или конца интервала, тип равен -1 для начала и +1 для конца. Таким образом, для каждого интервала добавляется два кортежа, по одному для начала и конца.
Сортировать таблицу по не убыванию смещения. (В случае одинакового смещения для двух кортежей противоположных типов (один интервал заканчивается с началом другого) применить специальный метод разрешения приоритета
[инициализация] best=0 cnt=0
[цикл] идти по таблице кортежей в порядке возрастания
[текущий номер перекрывающихся интервалов] cnt=cnt−type[i]
если cnt>best тогда best=cnt beststart=offset[i] bestend=offset[i+1]
комментарий: следующий кортеж [i+1] будет либо концом интервала с типом type=+1, что означает что это конец наилучшего на этот момент интервала или будет началом интервала с типом type=−1, который на следующем шаге станет лучшим.
[конец цикла] запомнить и вернуть интервал из кортежа [beststart, bestend] как оптимальный.
Количество ложных (не пересекающихся с определённым оптимальным интервалом) источников определить как общее количество источников за вычетом наилучших отобранных.
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.
IEEE STANDARD 1588—2008 — IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems
