El algoritmo de Marzullo , inventado por Keith Marzullo para su Ph.D. disertación en 1984, es un algoritmo de acuerdo utilizado para seleccionar fuentes para estimar el tiempo exacto a partir de una serie de fuentes de tiempo ruidosas . Una versión refinada de la misma, rebautizada como " algoritmo de intersección ", forma parte del protocolo de tiempo de red moderno . El algoritmo de Marzullo también se usa para calcular la intersección relajada de n cajas (o más generalmente n subconjuntos de R n ), como lo requieren varios métodos robustos de estimación de conjuntos .
Propósito
El algoritmo de Marzullo es eficiente en términos de tiempo para producir un valor óptimo a partir de un conjunto de estimaciones con intervalos de confianza donde el valor real puede estar fuera del intervalo de confianza para algunas fuentes. En este caso, se considera que la mejor estimación es el intervalo más pequeño consistente con el mayor número de fuentes.
Si tenemos las estimaciones 10 ± 2, 12 ± 1 y 11 ± 1, entonces estos intervalos son [8,12], [11,13] y [10,12] que se cruzan para formar [11,12] o 11,5 ± 0,5 como coherente con los tres valores.
Si, en cambio, los rangos son [8,12], [11,13] y [14,15], entonces no hay un intervalo coherente con todos estos valores, pero [11,12] es coherente con el mayor número de fuentes, es decir, dos de ellos.
Finalmente, si los rangos son [8,9], [8,12] y [10,12], entonces ambos intervalos [8,9] y [10,12] son consistentes con el mayor número de fuentes.
Este procedimiento determina un intervalo. Si el resultado deseado es el mejor valor de ese intervalo, entonces un enfoque ingenuo sería tomar el centro del intervalo como valor, que es lo que se especificó en el algoritmo original de Marzullo. Un enfoque más sofisticado reconocería que esto podría estar descartando información útil de los intervalos de confianza de las fuentes y que un modelo probabilístico de las fuentes podría devolver un valor diferente al centro.
Tenga en cuenta que el valor calculado probablemente se describa mejor como "optimista" en lugar de "óptimo". Por ejemplo, considere tres intervalos [10,12], [11, 13] y [11,99,13]. El algoritmo descrito a continuación calcula [11,99, 12] o 11,995 ± 0,005, que es un valor muy preciso. Si sospechamos que una de las estimaciones puede ser incorrecta, al menos dos de las estimaciones deben ser correctas. Bajo esta condición, la mejor estimación es [11,13] ya que este es el intervalo más grande que siempre interseca al menos dos estimaciones. El algoritmo que se describe a continuación se parametriza fácilmente con el número máximo de estimaciones incorrectas.
Método
El algoritmo de Marzullo comienza preparando una tabla de las fuentes, clasificándola y luego buscando (eficientemente) las intersecciones de intervalos. Para cada fuente hay un rango [c − r, c + r] definido por c ± r. Para cada rango, la tabla tendrá dos tuplas de la forma
La descripción del algoritmo utiliza las siguientes variables: best (mayor número de intervalos superpuestos encontrados), cnt (número actual de intervalos superpuestos), beststart y bestend (el principio y el final del mejor intervalo encontrado hasta ahora), i (un índice) y la tabla de tuplas.
- Construye la tabla de tuplas.
- Ordene la tabla por el desplazamiento. (Si existen dos tuplas con el mismo desplazamiento pero tipos opuestos, lo que indica que un intervalo termina justo cuando comienza otro, entonces es necesario un método para decidir cuál viene primero. Tal ocurrencia puede considerarse una superposición sin duración, que se puede encontrar por el algoritmo poniendo el tipo -1 antes del tipo +1. Si tales superposiciones patológicas se consideran objetables, pueden evitarse poniendo el tipo +1 antes de -1 en este caso).
- [inicializar] mejor = 0 cnt = 0
- [bucle] recorre cada tupla de la tabla en orden ascendente
- [número actual de intervalos superpuestos] cnt = cnt − tipo [i]
- si cnt> mejor entonces mejor = cnt mejor inicio = desplazamiento [i] bestend = desplazamiento [i + 1]
- comentario: la siguiente tupla, en [i + 1], será el final de un intervalo (tipo = + 1), en cuyo caso finaliza este mejor intervalo, o será el comienzo de un intervalo (tipo = −1 ) y en el siguiente paso reemplazará best.
- ambigüedad: no especificado es qué hacer si es mejor = cnt. Esta es una condición de un empate para una mayor superposición. Se puede tomar la decisión de tomar la menor de bestend-beststart y offset [i + 1] −offset [i] o simplemente tomar una arbitraria de las dos entradas igualmente buenas. Esta decisión es relevante solo cuando el tipo [i + 1] = + 1.
- [end loop] devuelve [beststart, bestend] como intervalo óptimo. El número de fuentes falsas (aquellas que no se superponen con el intervalo óptimo devuelto) es el número de fuentes menos el valor de best.
Eficiencia
El algoritmo de Marzullo es eficiente tanto en el espacio como en el tiempo. El uso del espacio asintótico es O (n) , donde n es el número de fuentes. Al considerar el requisito de tiempo asintótico, se puede considerar que el algoritmo consiste en construir la tabla, clasificarla y buscarla. La clasificación se puede realizar en tiempo O (n log n), y esto domina las fases de construcción y búsqueda que se pueden realizar en tiempo lineal . Por lo tanto, la eficiencia en el tiempo del algoritmo de Marzullo es O (n log n) .
Una vez que se ha creado y ordenado la tabla, es posible actualizar el intervalo para una fuente (cuando se recibe nueva información) en tiempo lineal. Por lo tanto, la actualización de los datos de una fuente y la búsqueda del mejor intervalo se pueden realizar en tiempo O (n).
Referencias
- Marzullo, KA (febrero de 1984). "Mantener el tiempo en un sistema distribuido: un ejemplo de un servicio distribuido débilmente acoplado" . Doctor. disertación . Departamento de Ingeniería Eléctrica. Universidad Stanford. ASIN B000710CSC . OCLC 38621764 . DDC 3781.1984 M.
enlaces externos
- Mills, David L. (5 de agosto de 2000). "Una breve historia de NTP Time: Confesiones de un cronometrador de Internet" (pdf) . EECIS . UDEL.
- "Keith Marzullo" . CSE . UCSD.