Алгоритм выбора оптимальных источников для оценки времени

Введение

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

Метод

При наличии M интервалов вида c ± r (что означает [c−r, c+r]), алгоритм стремится найти интервал, содержащий M−f источников. Значение f обозначается как число ложных срабатываний, то есть тех источников, которые ошибочны (фактическое значение находится за пределами доверительного интервала). Лучшая оценка – та, которая предполагает наименьшее количество ложных срабатываний, f. Результаты будут считаться допустимыми, если f < M/2, иначе алгоритм вернет ошибку вместо интервала. Алгоритм поиска пересечения начинается с создания таблицы кортежей <смещение, тип>. Для каждого интервала имеются три записи: нижняя граница, середина и верхняя граница, обозначенные типами −1, 0 и +1 соответственно. Таким образом, интервал c ± r приводит к записям <c−r, −1>, <c, 0> и <c+r, +1>. Затем эти записи сортируются по смещению. Переменные: Этот алгоритм использует f как число ложных срабатываний, endcount и midcount – целые числа. Lower и upper – значения смещений. [инициализация наилучшего f] Начать с f=0, предполагая, что все входные интервалы допустимы. Каждый раз, когда интервал не найден, f будет увеличиваться до тех пор, пока не будет найден интервал или f ≥ M/2. [инициализация] endcount=0 и midcount=0. [поиск нижней границы] Начать с начала списка (наименьшее смещение) и рассматривать каждый кортеж по порядку. endcount = endcount – type. Если endcount ≥ M−f, то lower = смещение и перейти к шагу 3, поскольку (возможная) нижняя граница найдена. Если type = 0, то midcount = midcount + 1. Повторить со следующим кортежем. Если достигнут конец списка, то перейти к шагу 6. [предварительная нижняя граница найдена, инициализация для поиска верхней границы] установить endcount = 0. [определение количества середин] Начать с конца списка и двигаться к меньшим смещениям. endcount = endcount + type. Если endcount ≥ M−f, то upper = смещение, перейти к шагу 5. Если type = 0, то midcount = midcount + 1. Повторить для следующего кортежа. Если достигнут конец списка, то перейти к шагу 6. Если lower ≤ upper и midcount ≤ f, то вернуть интервал [lower, upper] как результирующий доверительный интервал. [увеличение числа ложных срабатываний] f = f + 1. Если f ≥ M/2, то завершить работу и вернуть FAILED, иначе перейти к шагу 1.

Given M intervals of the form c ± r (which means [c−r,c+r]), the algorithm seeks to find an interval with M−f sources. The value f is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the confidence band). The best estimate is that which assumes the fewest falsetickers, f. The results will be considered valid if f < M/2, otherwise the algorithm will return failure instead of an interval. The intersection algorithm begins by creating a table of tuples <offset, type>. For each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types −1, 0 and +1 respectively. Thus the interval c ± r results in the entries <c−r,−1>, <c,0> and <c+r,+1>. These entries are then sorted by offset. Variables: This algorithm uses f as number of false tickers, endcount and midcount are integers. Lower and upper are values of offsets. [initialize best f] Start with f=0, assuming all input intervals are valid. Each time no interval is found f will be incremented until either an interval is found or f ≥ M/2. [initialize] endcount=0 and midcount=0. [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. endcount = endcount−type. If endcount ≥ M−f then lower = offset and goto step 3 because the (possible) lower endpoint has been found. If the type = 0 then midcount = midcount+1. Repeat with next tuple. If reach end of list then goto step 6. [tentative lower endpoint found, initialize to find upper endpoint] set endcount=0. [determine number of midpoints] Start from end of list and work towards lower offsets. endcount = endcount+type. If endcount ≥ M−f then upper = offset, goto step 5. If type = 0 then midcount = midcount+1. Repeat for next tuple. If reach end of list then goto step 6.
if lower ≤ upper and midcount ≤ f then return interval [lowerendpoint, upperendpoint] as resulting confidence interval. [increment number of falsetickers] f = f+1. If f ≥ M/2 then terminate and return FAILED, otherwise goto step 1.