Algoritmo de Berkeley

El algoritmo de Berkeley es un método de sincronización de relojes en computación distribuida que asume que ninguna máquina tiene una fuente de tiempo precisa. Fue desarrollado por Gusella y Zatti en la Universidad de California, Berkeley, en 1989. ^{[ 1 ]} Al igual que el algoritmo de Cristian , está diseñado para su uso dentro de intranets .

A diferencia del algoritmo de Cristian , el proceso servidor en el algoritmo de Berkeley, llamado líder , consulta periódicamente a otros procesos seguidores . En términos generales, el algoritmo es:

1. Se elige a un líder mediante un proceso electoral , como el algoritmo de Chang y Roberts .
2. El líder realiza una encuesta entre los seguidores , quienes responden con su tiempo de forma similar al algoritmo de Cristian .
3. El líder observa el tiempo de ida y vuelta (RTT) de los mensajes y estima el tiempo de cada seguidor y el suyo propio.
4. El líder calcula entonces el promedio de los tiempos registrados, ignorando cualquier valor que reciba que esté muy alejado de los valores de los demás.
5. En lugar de enviar la hora actualizada al otro proceso, el líder envía la cantidad (positiva o negativa) que cada seguidor debe ajustar en su reloj. Esto evita incertidumbre adicional debido al tiempo de ida y vuelta (RTT) en los procesos seguidores .

Con este método, el promedio compensa las tendencias de deriva de cada reloj individual. Gusella y Zatti publicaron resultados obtenidos con 15 ordenadores cuyos relojes se sincronizaron con una precisión de entre 20 y 25 milisegundos utilizando su protocolo.

Los sistemas informáticos normalmente evitan rebobinar su reloj cuando reciben una alteración negativa del reloj por parte del líder. Hacerlo rompería la propiedad de tiempo monótono, que es una suposición fundamental en ciertos algoritmos del propio sistema o en programas como make . Una solución simple a este problema es detener el reloj durante el tiempo especificado por el líder, pero esta solución simplista también puede causar problemas, aunque menos graves. Para correcciones menores, la mayoría de los sistemas ralentizan el reloj, aplicando la corrección durante un período de tiempo más largo.

A menudo, cualquier cliente cuyo reloj difiera en un valor fuera de la tolerancia establecida se descarta al promediar los resultados. Esto evita que la hora general del sistema se vea drásticamente alterada por un solo reloj erróneo.