Algoritmo de Cristian

Haz clic para ver el video del Algoritmo de Cristian

Algoritmo de Cristian

Este algoritmo está basado en el uso del tiempo coordenado universal (siglas en inglés, UTC), el cual es recibido por un equipo dentro del sistema distribuido. Este equipo, denominado receptor de UTC, recibe a su vez solicitudes periódicas del tiempo del resto de máquinas del sistema a cada uno de los cuales les envía una respuesta en el menor plazo posible informando el tiempo UTC solicitado, con lo cual todas las máquinas del sistema actualicen su hora y se mantenga así sincronizado todo el sistema. El receptor de UTC recibe el tiempo a través de diversos medios disponibles, entre los cuales se menciona las ondas de radio, Internet, entre otros. Un gran problema en este algoritmo es que el tiempo no puede correr hacia atrás:
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 éste recibe la respuesta.

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.

Funcionamiento del algoritmo

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.