Algoritmo de Berkeley

El algoritmo de Berkeley se trata de un algoritmo de sincronización de relojes diseñado por Gusella y Zatti en 1989.​ Dicho algoritmo se creó para entornos en los cuales no se tienen receptores de tiempo UTC, de forma que, gracias a este algoritmo se pueden mantener los relojes del entorno sincronizados con la misma hora.​ Este algoritmo sincroniza procesos en un sistema distribuido y garantiza que estos mismos se ejecuten de manera cronológica y secuencial (respetando el orden de los eventos en el sistema). Este algoritmo se categoriza como un algoritmo de sincronización de relojes físicos e internos. La base de todos estos tipos de algoritmos es la comunicación del tiempo de reloj de cada nodo. Cada uno calcula alguna función de tipo promedio o la mediana de todos los valores, si la diferencia con su reloj actual es mayor que la desviación máxima permitida se actualiza el reloj con el nuevo valor. Posteriormente el algoritmo se ejecutará de nuevo hasta lograr una convergencia de todos los nodos.

Introducción

Se trata de un algoritmo centralizado, en el que a diferencia de otros algoritmos como es el caso del algoritmo de Cristian, el servidor se va a elegir entre todos los equipos que se encuentran conectados en el entorno, el maestro solicita a los esclavos su hora periódicamente, una vez recibida la hora de los esclavos, el algoritmo de Berkeley se limitará a estimar su tiempo a partir de todos los computadores conectados, estimará la deriva que tiene cada reloj y procederá al envío de la corrección necesaria en cada caso.​

Funcionamiento del algoritmo

En el algoritmo de Berkeley, se procede a elegir un coordinador el cual tendrá el rol de maestro o lo que será lo mismo de servidor de tiempo. El coordinador en este algoritmo en diferencia con otros algoritmos de sincronización como es el caso del algoritmo de Cristian, no se mantendrá pasivo, se encargará de solicitar la hora del resto de equipos, los cuales tienen un rol de esclavos, dicha solicitud de hora se realizará de una forma periódica.

Una vez los esclavos hayan respondido con su hora local, el maestro realiza una estimación media de los retardos con los tiempos recibidos en los mensajes con cada uno de los equipos esclavos, obteniendo así un tiempo medio que relaciona las horas recibidas durante la solicitud y la hora propia del maestro.

Realizada dicha estimación, el siguiente paso será actualizar los relojes de los equipos esclavos. Para ello, el maestro enviará a cada esclavo el desfase que tiene respecto a la hora promedio que se ha calculado. Se envía el desfase en lugar de enviar la hora coordinada puesto que se debe tener en cuenta el error que aparecería por el tiempo de transmisión. Finalmente, cada equipo se limitará a actualizar su reloj adelantándolo en caso de ir con retraso o atrasándolo en caso de ir adelantado para aplicar la deriva recibida.

A continuación se añade una ilustración a modo esquemática para entender el funcionamiento del algoritmo de Berkeley.

Algoritmo de Berkeley.

​

Estudiando dicho algoritmo se puede pensar que no se tiene en cuenta el tiempo de propagación en la respuesta a la solicitud de la hora del esclavo a nuestro coordinador y por tanto, se recibe una hora con retraso. Dicha situación no es un escenario que se necesite tener en cuenta, puesto que la finalidad del algoritmo es la de calcular una hora promedio entre las que se reciben con el sondeo del maestro a todos sus esclavos. Además, en una red de área local entre los tiempos de propagación de mensajes entre maestro y los esclavos será despreciable y, por ello, no es necesario tener en cuenta.

El algoritmo de Berkeley realiza un promedio tolerante a fallos usando de base los tiempos enviados por los esclavos, lo cual significa que únicamente se toman para calcular el promedio los tiempos enviados por aquellos relojes cuya diferencia no difiere entre sí entre unos umbrales estipulados, de forma que se entenderá que el resto de relojes no están funcionando correctamente.​

En caso de fallo del maestro el proceso será el de elegir otro coordinador. Como fallo se entenderá que el maestro no realice las solicitudes de tiempo periódicas, no envíe a cada esclavo la deriva pertinente su reloj o simplemente que dote a los esclavos de un valor de deriva el cual no es muy lógico. Esto le da al algoritmo un enriquecimiento en robustez puesto que se puede añadir algoritmos de elección de un nuevo maestro en caso de caída o fallo del nodo maestro ya signado.

Pseudocódigo

1. 1. //Número de esclavos que participan en la sincronización x
2. 2. Nesclavos=x
3. 3. suma=0
4. 4. //Obtenemos el tiempo de los esclavos y calculamos la diferencia con el tiempo del
5. maestro
6. 5. tiempo_Esclavos[]=PedirTiempoEsclavos();
7. 6. for(i=0; i<Nesclavos;i++){
8. 7. diferencia_tiempos[i]= - tiempo_Esclavo[i] -TiempoMasterActual();
9. 8. }
10. 9. //Calculamos la diferencia media .
11. 10. for(i=0;i<Nesclavos;i++){
12. 11. suma+=diferencia_tiempos[i];
13. 12. }
14. //Debemos tener también en cuenta el servidor a la hora de hacer la media de ahí que sumemos +1
15. 13. diferencia_media=suma/(Nesclavos+1);
16. 14. //Calculamos tiempo de sincronización del maestro sumándole la deriva media.
17. 15. tiempo_sicronizacionMaestro= TiempoMasterActual()+ diferencia_media
18. 16. // Enviamos deriva de cada reloj para que ajuste su tiempo y se sincronicen.
19. 17. for(i=0;i<Nesclavos;i++){
20. 18. enviar_Deriva(diferencia_media, i )
21. 19. }

Inconvenientes​

·        En caso de que el maestro falle, dejará de preguntar la hora y, en consecuencia, se perderá la sincronización.

·        En el paso de mensajes entre maestro y esclavos y vicerversa se ha de tener en cuenta el retraso que genera el propio envío de los mensajes por lo que tendremos errores a la hora de sincronizar.

·        Otro de los problemas de ser un algoritmo centralizado será el de tener que elegir un nuevo maestro debido a que se puedan producir fallos en el tratamiento de los datos para llevar a a cabo la sincronización, buscando un maestro que cometa menor cantidad de fallos y el sistema se mantenga en correcto funcionamiento.

. La demora introducida por los equipos de conmutación, se agrava en los casos en los que el equipo cumple otras funciones además de conmutar paquetes, como es el caso de un PC que, además de actuar como conmutador, atiende otras tareas, con lo cual, la misma tarea de conmutar puede insumir diferentes tiempos.

Recursos

• Datos: Q269652