Алгоритм пересечения
begin clock-selection procedure
Каждый из партнеров просматривается последовательно и добавляется в конец списка, если он прошел ряд тестов. Для каждого из m кандидатов в список заносятся 3 записи в форме [указатель, тип]: [q - l, - 1], [q, 0] и [q + l, 1]. В результате в списке будет 3m записей, которые будут позднее упорядочены.
m
| for (each peer) | /*обращение ко всем партнерам */ |
if ({peer.reach ? 0 and peer.dispersion < ntp.maxdisperse} and not (peer.stratum > 1 И peer.refid = peer.hostaddr)) begin
l
| andistance (peer); | /* запись в список */ |
add [q - l, -1] to endpoint list;
add [q, 0] to endpoint list;
add [q + l, 1] to endpoint list;
m
<B>endif
endfor
| if (m = 0) begin | /* уход, если кандидаты отсутствуют */ |
sys.peer
sys.stratum
exit;
endif
sort endpoint list by increasing endpointtype;
Ниже приведенный алгоритм представляет собой адаптированную версию DTS [DEC89] и сконструирован так, чтобы отбирать только истинных кандидатов. Алгоритм начинается с инициализации значения f и занесения нуля в счетчики i и c. Затем, начиная с конца упорядоченного, для каждой записи [указатель, тип] значение типа вычитается из кода счетчика i, который содержит число пересечений. Если код типа равен нулю, инкрементируется значение c, которое регистрирует число ложных кандидатов. Если для некоторых записей i і ? m - f, конец записи становится нижней границей пересечения; в противном случае, f увеличивается на 1 и процедура повторяется. Без сброса значений f или c, аналогичная процедура используется для нахождения верхней границы, за исключением того, что значение кода тип добавляется к счетчику. Если после того как обе границы определены c Ј f, процедура продолжается для найденных m - f кандидатов, в противном случае, f увеличивается на 1 и вся процедура повторяется.
| for (f from 0 to f ? m/2) begin | /* обращение ко всем кандидатам */ |
c
i
| for (each [endpoint, type] from lowest) begin | /* нахождение нижней границы */ |
i
low
if (i ? m - f) break;
if (type = 0) c
endfor;
i
| for (each [endpoint, type] from highest) begin | /* нахождение верхней границы */ |
high
if (i ? m - f) break;
if (type = 0 ) c
endfor;
| if (c ? f) break; | /* продолжить, пока не будут найдены все ложные кандидаты */ |
| if (low > high) begin | /* завершить, если не найдено ни одного пересечения */ |
exit;
endif;
Заметим, что работа продолжается далее данной точки, только если имеется более m/2 пересечений. Однако возможно, но не слишком вероятно, что в области пересечения окажется менее m/2 кандидатов.
