Algoritmo de intersección

El algoritmo de intersección es un algoritmo de concordancia que se utiliza para seleccionar fuentes para estimar la hora con precisión a partir de varias fuentes de tiempo ruidosas . Forma parte del Protocolo de Tiempo de Red (NTP ) moderno . Es una forma modificada del algoritmo de Marzullo . ^{[ 1 ] [ 2 ]}

Si bien el algoritmo de Marzullo devuelve el intervalo más pequeño compatible con el mayor número de fuentes, este intervalo no necesariamente incluye el punto central (desplazamiento calculado) de todas las fuentes en la intersección. El algoritmo de intersección devuelve un intervalo que incluye el devuelto por el algoritmo de Marzullo, pero puede ser mayor, ya que incluye los puntos centrales. Este intervalo más amplio permite utilizar datos estadísticos adicionales para seleccionar un punto dentro del intervalo, lo que reduce la variabilidad en ejecuciones repetidas.

Dados M intervalos de la forma c  ± r (es decir, [ c − r , c + r ]), el algoritmo busca un intervalo con M − f fuentes. El valor f se refiere al número de falsos positivos, es decir, las fuentes que contienen errores (el valor real está fuera del intervalo de confianza ). La mejor estimación es aquella que supone el menor número de falsos positivos, f . Los resultados se considerarán válidos si f < M /2; de lo contrario, el algoritmo devolverá un error en lugar de un intervalo.   

El algoritmo de intersección comienza creando una tabla de tuplas <desplazamiento, tipo>. Para cada intervalo hay tres entradas: el extremo inferior, el punto medio y el extremo superior, etiquetados con los tipos −1 , 0 y +1 respectivamente. Así, el intervalo c  ± r da como resultado las entradas < c − r , −1 >, < c , 0> y < c + r , +1>. Estas entradas se ordenan luego por desplazamiento. 

Variables: Este algoritmo utiliza f como número de tickers falsos, endcount y midcount son números enteros. Lower y upper son valores de offsets.

0. [inicializar mejor f] Comience con f = 0, asumiendo que todos los intervalos de entrada son válidos. Cada vez que no se encuentre un intervalo, f se incrementará hasta que se encuentre un intervalo o f  ≥ M / 2. 
1. [inicializar] endcount = 0 y midcount = 0.
2. [encontrar el extremo inferior] Comience desde el principio de la lista (desplazamiento más bajo) considere cada tupla en orden. endcount  = endcount − type . Si endcount ≥ M − f entonces lower = offset y vaya al paso 3 porque se ha encontrado el extremo inferior (posible). Si type = 0 entonces midcount = midcount +1. Repita con la siguiente tupla. Si llega al final de la lista, vaya al paso 6.         
3. [Se encontró un punto final inferior tentativo, inicializar para encontrar el punto final superior] establecer endcount = 0.
4. [determinar el número de puntos medios] Comienza desde el final de la lista y avanza hacia desplazamientos menores. endcount  = endcount + type . Si endcount ≥ M − f, entonces upper = offset , ve al paso 5. Si type = 0, entonces midcount = midcount + 1. Repite para la siguiente tupla. Si llegas al final de la lista, ve al paso 6.         
5. Si lower  ≤ upper y midcount ≤ f, entonces devuelva interval [ lowerendpoint , upperendpoint ] como intervalo de confianza resultante.   
6. [incrementar el número de falsos tickers] f  = f +1. Si f ≥ M /2, entonces terminar y devolver FALLIDO, de lo contrario ir al paso 1.