Tiempos lógicos de Lamport

El algoritmo de los tiempos lógicos de Lamport, es un algoritmo simple usado para determinar el orden de los eventos en un Sistema Distribuido Informático. Este algoritmo se denomina así debido a que su creador fue uno de los científicos de la computación más relevantes, Leslie Lamport. Como sucede de manera habitual en un Sistema Distribuido, los diferentes nodos o procesos no estarán perfectamente sincronizados, por ello este algoritmo es usado para proporcionar un ordenamiento parcial de los eventos con una mínima sobrecarga de los recursos computacionales. Conceptualmente proporciona un primer paso de cara a un método más complejo y avanzado, llamado algoritmo de reloj vectorial (Vector clock).

Los algoritmos distribuidos que sincronizan recursos normalmente dependen de algún método de ordenación de eventos para funcionar. Por ejemplo, si consideramos un sistema con dos procesos y una memoria. Los procesos se envían mensajes el uno al otro, y también envían mensajes a memoria para solicitar acceso a la misma. El disco concede el acceso en el orden en el que los mensajes fueron enviados. Por ejemplo, el proceso A envía un mensaje a memoria solicitando una operación de escritura, y posteriormente envía una solicitud de escritura al proceso B. El proceso B recibe dicha solicitud, y como resultado manda a memoria su propio mensaje de solicitud de lectura. Si se produce un retardo, provocando que la memoria reciba los dos mensajes al mismo tiempo, esta deberá determinar qué mensaje ha ocurrido antes. El proceso A ocurrirá antes que el proceso B si se puede llegar de A hasta B mediante una secuencia de movimientos de dos tipos: avanzar mientras se mantiene en el mismo proceso o siguiendo un mensaje desde su envío hasta su recepción. Un algoritmo de reloj lógico proporciona un mecanismo para determinar el orden de los distintos eventos.

Lamport inventó un mecanismo por el cual el orden de los sucesos puede ser expresado de forma numérica. Un reloj lógico de Lamport es un contador de software asociado a cada proceso.

Conceptualmente, este reloj lógico es considerado como un reloj que tan solo tiene significado en el contexto de los mensajes enviados entre los procesos. Cuando un proceso recibe un mensaje, actualiza el valor de su reloj lógico en relación con el emisor de dicho mensaje.

Introducción al algoritmo​

El algoritmo sigue las siguientes reglas:

1. Un proceso incrementa su contador antes de cada evento que ocurra en ese proceso.
2. Cuando un proceso envía un mensaje, este incluye su contador en el envío.
3. Al recibir un mensaje, se actualiza el contador del receptor si es necesario, al mayor entre su propio contador y la marca de tiempo recibida en dicho mensaje.

En pseudocódigo el algoritmo para enviar un mensaje es:

reloj = reloj + 1;
marca_temporal_mensaje = reloj;
enviar(mensaje, marca_temporal_mensaje);

Algoritmo para la recepción del mensaje:

recibir() = (mensaje, marca_temporal_mensaje);
reloj = max(marca_temporal_mensaje,reloj) + 1;

Consideraciones​

Sean ‘a’ y ‘b’ dos eventos del mismo proceso y C(x) la marca de tiempo de un cierto evento x, C(a) nunca puede ser igual que C(b).

Por lo tanto, es necesario que:

• El reloj lógico debe ser configurado de forma que C(a) y C(b) deben diferir como mínimo en un instante de tiempo.
• ​ En un entorno multiproceso o multihilo, sean dos eventos que suceden en tiempos lógicos de Lamport Ti y Tj en los procesos Pi y Pj, respectivamente:

(Ti, i) < (Tj, j) si Ti < Tj o Ti = Tj y i < j

Básicamente, es un modo de ‘desempatar’ tiempos lógicos iguales mediante el identificador de proceso.

Implicaciones​

Un reloj de Lamport se utiliza para crear un ordenamiento parcial y causal de los eventos entre procesos. Ofrece un reloj lógico que cumple las reglas que veremos a continuación.

La relación siguiente es cierta: si a → b entonces C(a) < C(b), donde → significa cual ocurrió antes. Esta relación solo tiene una dirección, llamada condición de consistencia del reloj: si un evento ocurre antes que otro, el reloj lógico de dicho evento también ocurre antes que el del otro. Hay una fuerte condición de consistencia del reloj, que es bidireccional (si C(a) < C(b) entonces a → b) puede ser obtenida utilizando otras técnicas, como por ejemplo el reloj vectorial. Si solo usamos un reloj simple de Lamport, solo se puede obtener un orden causal y parcial como se comentó anteriormente.

No obstante, los tiempos de Lamport pueden ser usados para crear un orden total de eventos en un sistema distribuido usando un mecanismo arbitrario que permita romper relaciones.

Ordenamiento causal​

Para dos eventos cualesquiera, a y b, si existe alguna manera en la que a pueda influir en b, entonces el tiempo de Lamport de a será menor que el tiempo de Lamport de b. Es posible también tener dos eventos y no poder determinar cuál de ellos ocurrió primero, esto ocurre cuando ambos eventos no se ven afectados el uno por el otro. Si a y b no han sido afectados entre sí, no se puede afirmar nada sobre su ordenación o causalidad.

Reloj lógico de Lamport en Sistemas Distribuidos​

En un Sistema Distribuido no es posible sincronizar en la práctica a través de procesos en el sistema, por lo tanto, dichos procesos utilizan un reloj lógico basado en eventos para comunicarse. Si dos procesos no intercambian mensajes, entonces no necesitan un reloj común, los eventos que ocurren en estos procesos se denominan eventos concurrentes.

Los procesos de la misma máquina se pueden ordenar basándose en el reloj del sistema. Cuando dos procesos se comunican mediante el envío de un mensaje, se puede decir que el evento que realiza el envío ocurre antes que el evento de recepción. Se debe establecer un orden lógico entre los eventos.

Se dice que un Sistema Distribuido tiene un orden parcial si existe una relación de orden parcial entre los eventos de dicho sistema. Si se puede establecer una relación causal entre todos los eventos del sistema, entonces se dice que el sistema tiene un orden total.

Dos eventos del mismo proceso no pueden ocurrir simultáneamente. Si el sistema tiene un orden total, podemos determinar el orden entre todos los eventos del sistema. Si el sistema tiene un orden parcial entre los procesos, que es el orden que proporciona el reloj lógico de Lamport, entonces solo podremos determinar el orden entre los procesos que interactúan. Lamport trató la ordenación de dos eventos con la misma marca de tiempo. De este modo, dos marcas de tiempo pueden ser iguales en un Sistema Distribuido, pero si aplicamos el algoritmo del reloj lógico los eventos ocurrirán manteniendo un orden parcial estricto.

El reloj lógico de Lamport nos lleva a una situación en la que todos los eventos en un Sistema Distribuido están totalmente ordenados. Esto quiere decir, si a → b, entonces a ocurrió antes que b. Desafortunadamente, con el reloj de Lamport, no podemos conocer el tiempo real de a y b. Si el reloj lógico indica a → b, esto no significa que a haya ocurrido antes que b en términos de tiempo real. El problema de los relojes de Lamport es que no capturan la causalidad.​

Si sabemos que a → c y b → c no podemos conocer que evento inició c.

​ Si a → b y b → c, entonces a → c (propiedad transitiva). a → a siempre es falso.

Este tipo de información puede ser importante cuando intentamos reproducir eventos en un Sistema Distribuido. La teoría dice que, si un nodo se cae, si conocemos la relación causal entre los mensajes, entonces podremos reproducir dichos mensajes y respetar la relación causal para llevar al nodo al estado en el que estaba.

Referencias

• Datos: Q1801707