Each peer is examined in turn and added to an endpoint list only if it passes several sanity checks designed to avoid loops and use of exceptionally noisy data. If no peers survive the sanity checks, the procedure exits without finding a synchronization source. For each of m survivors three entries of the form [endpoint,type] are added to the endpoint list: [ THETA- LAMBDA ,-1], [ THETA ,0] and [ THETA + LAMBDA ,1]. There will be 3 m entries on the list, which is then sorted by increasing endpoint.
m <-- 0; for (each peer) /* calling all peers */ if (peer.reach != 0 and peer.dispersion < NTP.MAXDISPERSE and not (peer.stratum > 1 and peer.refid = peer.hostaddr)) begin LAMBDA andistance (peer); /* make list entry */ add [THETA - LAMBDA ,-1] to endpoint list; add [THETA ,0] to endpoint list; add [THETA + LAMBDA ,1]> to endpoint list; m <-- m+1; endif endfor if (m = 0) begin /* skedaddle if no candidates */ sys.peer <-- NULL; sys.stratum <-- 0 (undefined); exit; endif sort endpoint list by increasing endpoint||type;
The following algorithm is adapted from DTS [DEC89] and is designed to produce the largest single intersection containing only truechimers. The algorithm begins by initializing a value f and counters i and c to zero. Then, starting from the lowest endpoint of the sorted endpoint list, for each entry [endpoint,type] the value of type is subtracted from the counter i, which is the number of intersections. If type is zero, increment the value of c, which is the number of falsetickers (see Appendix H). If i >= m- f for some entry, endpoint of that entry becomes the lower endpoint of the intersection; otherwise, f is increased by one and the above procedure is repeated. Without resetting f or c, a similar procedure is used to find the upper endpoint, except that the value of type is added to the counter.. If after both endpoints have been determined c <=f , the procedure continues having found m - f truechimers; otherwise, f is increased by one and the entire procedure is repeated.
for (f from 0 to f >= m over 2) begin /* calling all truechimers */ c <-- 0; i <-- 0; for (each [endpoint, type] from lowest) begin /* find low endpoint */ i <-- i - type; low <-- endpoint; if (i >= m - f) break; if (type = 0) c <-- c + 1 ; endfor; i <-- 0;
for (each [endpoint, type] from highest) begin /* find high endpoint */ i <-- i + type; high <-- endpoint; if ( i >= m - f ) break; if ( type = 0) c <-- c + 1; endfor; if ( c <= f) break; /* continue until all falsetickers found */ endfor; if ( low > high) begin /* quit if no intersection found */ sys.peer <- NULL; exit; endif;
Note that processing continues past this point only if there are more than m over 2 intersections. However, it is possible, but not highly likely, that there may be fewer than m over 2 truechimers remaining in the intersection.