Algoritmo de Lamport para la Sincronización de Relojes Lógicos en Sistemas Distribuidos

La sincronización en sistemas distribuidos consiste en garantizar que los procesos se ejecuten en forma cronológica y a la misma vez respetar el orden de los eventos dentro del sistema. En el caso de sistemas de una sola CPU, este problema se resuelve usando semáforos, pero en sistemas de múltiples CPUs la solución ya implica el uso de otros métodos o algoritmos, para garantizar no solo la comunicación entre procesos sino también la forma como estos cooperan entre sí.

Esta sincronización, en sistemas distribuidos, se hace más compleja que en los sistemas centralizados puesto que la información y el procesamiento se mantienen en diferentes nodos. La sincronización de relojes en sistemas distribuidos nos permite garantizar que los procesos se ejecutan cronológicamente y además respetar el orden de los eventos dentro del sistema.

Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo reloj. Es un cronómetro consistente en un cristal de cuarzo de precisión sometido a una tensión eléctrica.

Para una computadora y un reloj no interesan pequeños desfasajes del reloj porque:

Todos los procesos de la máquina usan el mismo reloj y tendrán consistencia interna.
Importan los tiempos relativos.

Para varias computadoras con sus respectivos relojes:

Es imposible garantizar que los cristales de computadoras distintas oscilen con la misma frecuencia.
Habrá una pérdida de sincronía en los relojes (de software), es decir que tendrán valores distintos al ser leidos.

"La diferencia entre los valores del tiempo se llama distorsión del reloj y podría generar fallas en los programas dependientes del tiempo."

Luego de esta pequeña introducción a la sincronización vamos a hablar acerca del Algoritmo de Lamport. Y es que en este post hablaremos de la propuesta que hizo el científico en computación Dr Leslie Lamport.

Lamport señaló que la sincronización de relojes no tiene que ser absoluta.

Si 2 procesos no interactúan no es necesario que sus relojes estén sincronizados.

Generalmente lo importante no es que los procesos estén de acuerdo en la hora, pero sí importa que coincidan en el orden en que ocurren los eventos.

Y es aquí dónde aparece el concepto de reloj lógico. Un reloj lógico de Lamport es un contador software que se incrementa monótonamente, cuyos valores no necesitan tener ninguna relación particular con ningún reloj físico.

Para sincronizar los relojes lógicos, Lamport definió la relación ocurre antes de(happens-before):

Si “a” y “b” son eventos en el mismo proceso y “a” ocurre antes de “b”, entonces “a –> b” es verdadero.

“Ocurre antes de” es una relación transitiva:

Si “a –> b” y “b –> c”, entonces “a –> c”.

Si dos eventos “x” e “y” están en procesos diferentes que no intercambian mensajes, entonces “x –> y” no es verdadero, pero tampoco lo es “y –> x”:

Se dice que son eventos concurrentes.

Necesitamos una forma de medir el tiempo tal que a cada evento “a”, le podamos asociar un valor del tiempo “C(a)” en el que todos los procesos estén de acuerdo:

Se debe cumplir que:

o Si “a –> b” entonces “C(a) < C(b)”.

o El tiempo del reloj, “C”, siempre debe ir hacia adelante (creciente), y nunca hacia atrás (decreciente).

El algoritmo de Lamport asigna tiempos a los eventos.

Una vez descrito el algoritmo, pasaré a mostrar su implementación en java. La primera imágen corresponde a una simulación similar a la mostrada en la imágen anterior y que puede ayudarnos a comprender mejor el funcionamiento de este algoritmo.

En la imágen siguiente, vemos que al querer enviar un mensaje del proceso 3 en un instante de tiempo 4 al proceso 2 en un instante de tiempo 3, el algoritmo exige la sincronización de los relojes logicos de los CPUs donde se encuentran los procesos anteriormente numerados. Basta dar clic en el botón sincronizar para ver los cambios en los vectores de tiempo de ambos procesos, mientras que el resto de procesos no sufren alteración alguna, tal y como lo describe el algoritmo de Lamport.

Espero que la explicación y esta simulación(que puedes descargar aquí) te sean de utilidad. También pueden revisar este post relacionado a los algoritmos de planificación y paginación de procesos.