Algoritmo de Cristian

El algoritmo de Cristian (1989) es un método, dentro de la computación distribuida, para la sincronización de relojes. Cristian describe el método como probabilístico debido a que se consigue sincronización solo si el tiempo de respuesta es suficientemente corto comparado con la precisión requerida.​ Consiste en un servidor conectado a una fuente de UTC y unos clientes que se sincronizan con dicho servidor.

Introducción

La sincronización de relojes en un sistema distribuido consiste en garantizar que los procesos se ejecuten de forma cronológica y a la misma vez respetar el orden de los eventos dentro del sistema. Existen dos tipos de sincronización de relojes físicos:

• Sincronización externa: consiste en sincronizar los relojes de los procesos C_i con una fuente de tiempo externa fiable.

|S(t) – C_i(t)| < D ; siendo D un límite mayor que cero y S una fuente de tiempo UTC.

• Sincronización interna: si los relojes C_i están sincronizados entre ellos con un conocido grado de precisión y no necesariamente sincronizados con una fuente externa de tiempo.

|C_i(t) - C_j(t) | < D ; siendo D un límite mayor que cero.

Sincronización interna en un sistema síncrono

En un sistema síncrono son conocidos:

• Los límites de deriva de los relojes.
• El máximo retardo de transmisión de mensajes.
• Tiempo para ejecutar cada paso de un proceso.

El proceso seguido para la sincronización entre dos procesos es el siguiente:

1. Un proceso envía el tiempo t de su reloj local a otro proceso en un mensaje m.
2. El proceso receptor puede actualizar su reloj con el tiempo t + T_TRANS al recibir el mensaje, donde T_TRANS es el tiempo empleado en transmitir el mensaje m entre ellos.

T_TRANS es desconocido y no se puede determinar pues depende del tráfico de red .Pese a ello se puede establecer un mínimo tiempo de transmisión, que se obtiene cuando no hay tráfico en la red ni otros procesos, y un máximo estimado.

La incertidumbre en el tiempo de transmisión del mensaje se define como u =(max – min).

• Si el receptor coloca su reloj a t + min el sesgo del reloj puede ser como mucho u.
• Si el receptor coloca su reloj a t + max el sesgo del reloj puede ser como mucho u.
• Si el receptor coloca su reloj a t + (max + min)/2 el sesgo es como mucho u/2.

En general, para un sistema síncrono el error óptimo cuando se sincronizan N relojes es u( 1-1/N). La mayoría de los sistemas distribuidos son asíncronos y no tienen definido un límite máximo para la transmisión de mensajes por lo tanto:

T_TRANS = min + x ; el valor de x es mayor o igual que cero y depende de cada caso en particular.

Funcionamiento del algoritmo

El Algoritmo de Cristian propone realizar la sincronización de los relojes de múltiples máquinas utilizando una máquina externa que cuente con un reloj más preciso, posiblemente sincronizado otros aún más precisos. Partimos de un sistema distribuido con varios nodos i, cada uno de ellos cuenta con un reloj local Ci. En cualquier instante t se cumple para todos los nodos Ci(t) = t, es decir, todos los relojes locales tienen la misma hora y coinciden con la hora “verdadera”. El algoritmo de Cristian sirve para sincronizar el reloj local de un ordenador cliente (CC) con el reloj local de un ordenador servidor (CS).​

1. Un proceso p hace una petición de tiempo al servidor en un mensaje m_r.
2. El servidor responde con un mensaje m_t en el que incluye su tiempo T_UTC.
3. El proceso que recibe el mensaje m_t actualiza su reloj con el tiempo T_UTC, pero hay que considerar el error cometido pues se ha requerido un tiempo para la transmisión del mensaje desde el servidor.

Se mide el tiempo que se tarda en recibir la respuesta desde que de envía el mensaje de petición, T_VIAJE. El tiempo estimado de propagación, en ausencia de otra información, será T_VIAJE /2 por lo que el cliente sincroniza su reloj a T_UTC + T_VIAJE/2. Esta estimación puede mejorarse si se conoce el tiempo mínimo de propagación del mensaje:

• El tiempo mínimo en el que el servidor escribió el mensaje es min.
• El tiempo máximo en el que el servidor escribió el mensaje es T_VIAJE – min.

Por lo tanto el tiempo en el que el mensaje del servidor es recibido se sitúa en el rango [C_UTC + min, C_UTC+ T_VIAJE –min ] cuya anchura es T_VIAJE – 2min así que la precisión es ± T_VIAJE/2 – min.

Imagen del proceso del algoritmo

Consideraciones

• Los relojes no deben retroceder para evitar errores
• La sincronización requiere del intercambio de mensajes, pero el tránsito de estos consume tiempo.
• El tiempo del receptor UTC no puede ser menor que el tiempo de la máquina que le solicitó el tiempo.
• El servidor de UTC debe procesar las solicitudes de tiempo con el concepto de interrupciones, lo cual incide en el tiempo de atención.
• El intervalo de transmisión de la solicitud y su respuesta debe ser tomado en cuenta para la sincronización.
• El tiempo de propagación se suma al tiempo del servidor para sincronizar al emisor cuando ´este recibe la respuesta.

Inconvenientes

1. El problema que se presenta es la posibilidad de fallo debido a la existencia de un único servidor. Cristian sugiere múltiples servidores de tiempo sincronizados que suministren el tiempo. El cliente envía un mensaje de petición a todos los servidores y toma la primera respuesta recibida.
2. El algoritmo no contempla problemas de malfuncionamiento o fraude por parte del servidor.
3. La capacidad de cada nodo para leer el valor del reloj de otro nodo puede generar errores debido al retraso en la comunicación de mensajes entre nodos. La demora se puede calcular tomando en cuenta el tiempo necesario para preparar, transmitir y recibir un mensaje vacío en ausencia de errores de transmisión y carga del sistema.

Bibliografía

• G. Colouris, J. Dollimore, T. Kindberg and G. Blair. Distributed Systems: Concepts and Design (5th Ed). Addison-Wesley, 2011
• Cristian, F. (1989), «Probabilistic clock synchronization», Distributed Computing (Springer) 3 (3): 146--158
• Romero, F., & Tinetti, F. (2009). Sincronización de relojes en ambientes Distribuidos.

• Datos: Q798919