El algoritmo de intersección es un algoritmo de acuerdo que se utiliza para seleccionar fuentes para estimar el tiempo exacto a partir de una serie de fuentes de tiempo ruidosas . Forma parte del protocolo de tiempo de red moderno . Es una forma modificada del algoritmo de Marzullo . [1] [2]
Si bien el algoritmo de Marzullo devolverá el intervalo más pequeño consistente con el mayor número de fuentes, el intervalo devuelto no incluye necesariamente 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 incluirá los puntos centrales. Este intervalo más grande permite usar datos estadísticos adicionales para seleccionar un punto dentro del intervalo, reduciendo la fluctuación en la ejecución repetida.
Método
Dados M intervalos de la forma c ± r (que significa [ c - r , c + r ]), el algoritmo busca encontrar un intervalo con M - f fuentes. El valor f se conoce como el número de falseticers, aquellas fuentes que están en error (el valor real está fuera de la banda de confianza ). La mejor estimación es la que supone la menor cantidad de falsetes, 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
Variables: este algoritmo utiliza f como número de falsos tickers, el recuento final y medio son números enteros. Inferior y superior son valores de compensaciones.
- [inicializar mejor f] Empiece con f = 0, asumiendo que todos los intervalos de entrada son válidos. Cada vez que no se encuentre ningún intervalo, f se incrementará hasta que se encuentre un intervalo o f ≥ M / 2.
- [initialize] endcount = 0 y midcount = 0.
- [encontrar el punto final inferior] Empiece al principio de la lista (desplazamiento más bajo) considere cada tupla en orden. endcount = endcount - tipo . Si el recuento final ≥ M - f entonces inferior = desplazamiento y vaya al paso 3 porque se ha encontrado el (posible) punto final inferior. Si el tipo = 0, midcount = midcount +1. Repita con la siguiente tupla. Si llega al final de la lista, vaya al paso 6.
- [punto final inferior tentativo encontrado, inicializar para encontrar el punto final superior] set endcount = 0.
- [determinar el número de puntos medios] Empiece desde el final de la lista y trabaje hacia compensaciones más bajas. endcount = endcount + tipo . Si el recuento final ≥ M - f entonces superior = desplazamiento , vaya al paso 5. Si type = 0, entonces midcount = midcount +1. Repita para la siguiente tupla. Si llega al final de la lista, vaya al paso 6.
- si el recuento inferior ≤ superior y medio ≤ f , el intervalo de retorno [punto inferior , punto superior ] como intervalo de confianza resultante.
- [Incremento del número de falseadores] f = f +1. Si f ≥ M / 2, termine y regrese FAILED; de lo contrario, vaya al paso 1.
Referencias
- ^ "RFC 1305 - Especificación, implementación y análisis del protocolo de tiempo de red (versión 3)" . tools.ietf.org . 2013 . Consultado el 6 de octubre de 2013 .
Especificación funcional del servicio horario digital versión T.1.0.5. Corporación de equipos digitales, 1989.
- ^ Especificación funcional del servicio de hora digital, versión T.1.0.5. Corporación de equipos digitales, 1989.