Algoritmos para la escritura y lectura de relojes

En un sistema distribuido ¿Qué algoritmos existen para la escritura y lectura de relojes?

Los algoritmos para la sincronización dependen principalmente del reloj usado, entonces podemos categorizar estos de acuerdo al reloj:

• Relojes físicos: Estos son los que disponen los propios computadores, son dispositivos electrónicos que cuentan las oscilaciones que ocurren en un cristal a una frecuencia definida. Para mantener estos relojes sincronizados entre sí podemos usar los siguientes algoritmos:
  • Algoritmo de Cristian: Se utiliza un servidor de tiempo, conectado a un dispositivo que recibe señales de una fuente de UTC, para sincronizar computadores externamente. Bajo solicitud, el proceso S proporciona el tiempo de acuerdo con su reloj. Sus principales características de este algoritmo son:
    • Es adecuado para sincronización con UTC.
    • El tiempo de transmisión del mensaje es (T1 – T0)/2
    • El tiempo en propagar el mensaje es (T1 – T0 – I)/2
    • El valor que devuelve el servidor se incrementa en (T1 – T0 – I)/2
    • Para mejorar la precisión se pueden hacer varias mediciones y descartar cualquiera en la que T1 – T0 exceda de un límite.
    • Donde I es el tiempo del manejador de interrupciones.
  • Algoritmo de Berkeley: Se elige un computador coordinador para actuar como maestro, este computador consulta periódicamente a los otros computadores cuyos relojes están para ser sincronizados, llamadas esclavos. Los esclavos le devuelven sus valores de reloj. El maestro estima sus tiempos locales de reloj observando los tiempos de ida y vuelta, y promedia los valores obtenidos. Sus principales características son:
    • El servidor de tiempo realiza un muestreo periódico de todas las máquinas para pedirles el tiempo.
    • Calcula el tiempo promedio e indica a todas las máquinas que avancen su reloj a la nueva hora o que disminuyan la velocidad.
    • Si cae el servidor entonces selecciona uno nuevo con el algoritmo de elección.
• Relojes lógicos: Es un contador software que se incrementa monótonamente, cuyos valores no necesitan tener ninguna relación particular con ningún reloj físico. Dentro de estos relojes se encuentran los relojes vectoriales. Para mantener estos relojes sincronizados entre sí podemos usar el siguiente algoritmo:
  • Algoritmo de Lamport: Nos asegura que si el evento “a” ocurre antes del evento “b” entonces el valor del tiempo del evento “a” es menor al valor del tiempo del evento “b”. También nos asegura que el valor del tiempo del reloj siempre debe ser creciente. En otras palabras este algoritmo asigna tiempo a los eventos.
  • Un caso más especial de estos relojes lógicos son los relojes vectoriales(vector de N enteros para un sistema de N procesos), estos implementan el siguiente algoritmo:
    • Algoritmo de Mattern y Fidge: Nos permite siempre evaluar si dos marcas de tiempo tienen o no relación de precedencia.