Алгоритм Марзулло

Алгоритм Марзулло — это алгоритм согласования данных, использующийся для выбора более точных источников для оценки точного времени из ряда источников времени, разной степени точности и усреднения времени, полученными от разных NTP-серверов. Переработанная версия этого алгоритма, названная «алгоритмом пересечений», является частью сетевого протокола для синхронизации времени (NTP).

Изобретён Кейтом Марзулло в рамках своей кандидатской диссертации в 1984 году.

Алгоритм позволяет сводить к минимуму влияние данных от заведомо некорректно настроенных NTP-серверов на общую систему.

ОписаниеПравить

Алгоритм Марзулло эффективен (в терминах времени) для получения оптимального значения из множества оценок с их доверительными интервалами. Важно, что для некоторых источников оптимальное значение может лежать вне доверительного интервала. Наилучшей оценкой следует считать наименьший интервал, соответствующий наибольшему числу источников.

Предположим, что мы имеем следующие оценки: 10 ± 2, 12 ± 1 и 11 ± 1 в интервалах [8,12], [11,13] и [10,12]. Их пересечением будет интервал [11,12] или точка 11.5 ± 0.5, соответствующая всем трём источникам.


Распишем алгоритм по шагам:

  1. Построить таблицу кортежей
  2. Сортировать таблицу по смещению. (В случае одинакового смещения для двух кортежей противоположных типов (один интервал заканчивается с началом другого) применить специальный метод разрешения приоритета.
  3. [инициализация] best=0 cnt=0
  4. [цикл] идти по таблице кортежей в порядке возрастания
  1. [текущий номер перекрывающихся интервалов] cnt=cnt−type[i]
  2. если cnt>best тогда best=cnt beststart=offset[i] bestend=offset[i+1]

комментарий: следующий кортеж [i+1] будет либо концом интервала с типом type=+1, что означает что это конец наилучшего на этот момент интервала или будет началом интервала с типом type=−1, который на следующем шаге станет лучшим.

  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

СсылкиПравить