Marca de tiempo de Lamport

El algoritmo de marca de tiempo de Lamport es un algoritmo de reloj lógico simple que se utiliza para determinar el orden de los eventos en un sistema informático distribuido . Como los diferentes nodos o procesos normalmente no estarán perfectamente sincronizados, este algoritmo se utiliza para proporcionar un orden parcial de eventos con una sobrecarga mínima, y proporciona conceptualmente un punto de partida para el método de reloj vectorial más avanzado . El algoritmo lleva el nombre de su creador, Leslie Lamport .

Los algoritmos distribuidos, como la sincronización de recursos, a menudo dependen de algún método de ordenar los eventos para que funcionen. Por ejemplo, considere un sistema con dos procesos y un disco. Los procesos se envían mensajes entre sí y también envían mensajes al disco solicitando acceso. El disco otorga acceso en el orden en que se recibieron los mensajes . Por ejemplo, el proceso envía un mensaje al disco solicitando acceso de escritura y luego envía un mensaje de instrucción de lectura al proceso . El proceso recibe el mensaje y, como resultado, envía su propio mensaje de solicitud de lectura al disco. Si hay una demora en el tiempo que hace que el disco reciba ambos mensajes al mismo tiempo, puede determinar qué mensaje sucedió antes que el otro: sucede antes ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ si se puede pasar del a mediante una secuencia de movimientos de dos tipos: avanzar permaneciendo en el mismo proceso, y seguir un mensaje desde su envío hasta su recepción. Un algoritmo de reloj lógico proporciona un mecanismo para determinar hechos sobre el orden de tales eventos. Tenga en cuenta que si dos eventos ocurren en procesos diferentes que no intercambian mensajes directa o indirectamente a través de procesos de terceros, entonces decimos que los dos procesos son concurrentes, es decir, no se puede decir nada sobre el orden de los dos eventos. ^[1] ${\ Displaystyle A}$ ${\ Displaystyle B}$

Lamport inventó un mecanismo simple mediante el cual el pedido sucedido antes se puede capturar numéricamente. Un reloj lógico de Lamport es un valor de contador de software numérico que se mantiene en cada proceso.

Conceptualmente, este reloj lógico puede concebirse como un reloj que solo tiene significado en relación con los mensajes que se mueven entre procesos. Cuando un proceso recibe un mensaje, vuelve a sincronizar su reloj lógico con ese remitente. El reloj vectorial mencionado anteriormente es una generalización de la idea en el contexto de un número arbitrario de procesos independientes paralelos.

Algoritmo

El algoritmo sigue algunas reglas simples:

Un proceso incrementa su contador antes de cada evento local (por ejemplo, evento de envío de mensajes);
Cuando un proceso envía un mensaje, incluye su valor de contador con el mensaje después de ejecutar el paso 1;
Al recibir un mensaje, el contador del destinatario se actualiza, si es necesario, al mayor de su contador actual y la marca de tiempo en el mensaje recibido. Luego, el contador se incrementa en 1 antes de que el mensaje se considere recibido. ^[2]

En pseudocódigo , el algoritmo de envío es:

# evento es conocido
tiempo = tiempo + 1;
# evento ocurre
enviar (mensaje, hora);

El algoritmo para recibir un mensaje es:

(mensaje, marca de tiempo) = recibir ();
time = max (marca_tiempo, hora) + 1;

Consideraciones

Por cada dos eventos diferentes y ocurriendo en el mismo proceso, y siendo la marca de tiempo de un evento determinado , es necesario que nunca sea igual . ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle C (x)}$ ${\ Displaystyle x}$ ${\ Displaystyle C (a)}$ ${\ Displaystyle C (b)}$

Por tanto es necesario que:

El reloj lógico debe configurarse de modo que haya un mínimo de un "tic" de reloj (incremento del contador) entre eventos y ; ${\ Displaystyle a}$ ${\ Displaystyle b}$
En un entorno multiproceso o multiproceso, puede ser necesario adjuntar el ID de proceso (PID) o cualquier otro ID único a la marca de tiempo para que sea posible diferenciar entre eventos y cuáles pueden ocurrir simultáneamente en diferentes procesos. ${\ Displaystyle a}$ ${\ Displaystyle b}$

Orden causal

Para dos eventos cualesquiera y , si hay alguna forma que pudiera haber influido , entonces la marca de tiempo de Lamport de será menor que la marca de tiempo de Lamport de . También es posible tener dos eventos en los que no podemos decir cuál fue primero; cuando eso sucede, significa que no podrían haberse afectado entre sí. Si y no pueden tener ningún efecto el uno en el otro, entonces no importa cuál fue el primero. ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle a}$ ${\ Displaystyle b}$

Trascendencia

Se puede usar un reloj de Lamport para crear un orden causal parcial de eventos entre procesos. Dado un reloj lógico que sigue estas reglas, la siguiente relación es verdadera: si entonces , donde significa que sucedió antes . ${\ displaystyle a \ rightarrow b}$ ${\ Displaystyle C (a) <C (b)}$ $\rightarrow \,$

Esta relación solo es en una dirección, y se llama condición de consistencia del reloj : si un evento viene antes que otro, entonces el reloj lógico de ese evento viene antes que el del otro. La condición de coherencia de reloj fuerte , que es bidireccional (si es así ), se puede obtener mediante otras técnicas, como los relojes vectoriales. Usando solo un reloj Lamport simple, solo se puede inferir un orden causal parcial del reloj. $C(a)<C(b)$ $a\rightarrow b$

Sin embargo, a través del contrapositivo , es cierto que eso implica . Entonces, por ejemplo, si entonces no puede haber sucedido antes . $C(a)\nless C(b)$ $a\nrightarrow b$ $C(a)\geq C(b)$ $a$ $b$

Otra forma de decir esto es que significa que puede haber sucedido antes , o ser incomparable con el pedido sucedido antes , pero no sucedió después . $C(a)<C(b)$ $a$ $b$ $b$ $a$ $b$

Sin embargo, las marcas de tiempo de Lamport se pueden usar para crear un orden total de eventos en un sistema distribuido usando algún mecanismo arbitrario para romper los lazos (por ejemplo, el ID del proceso). La advertencia es que este ordenamiento es un artefacto y no se puede depender de él para implicar una relación causal.

El reloj lógico de Lamport en sistemas distribuidos

En un sistema distribuido, en la práctica no es posible sincronizar el tiempo entre entidades (generalmente consideradas como procesos) dentro del sistema; de ahí que las entidades puedan utilizar el concepto de reloj lógico basado en los eventos a través de los cuales se comunican.

Si dos entidades no intercambian ningún mensaje, probablemente no necesiten compartir un reloj común; los eventos que ocurren en esas entidades se denominan eventos concurrentes.

Entre los procesos en la misma máquina local podemos ordenar los eventos basados en el reloj local del sistema.

Cuando dos entidades se comunican mediante el paso de mensajes, se dice que el evento de envío ocurre antes del evento de recepción, y se puede establecer el orden lógico entre los eventos.

Se dice que un sistema distribuido tiene orden parcial si podemos tener una relación de orden parcial entre los eventos del sistema. Si se puede establecer la "totalidad", es decir, la relación causal entre todos los eventos del sistema, se dice que el sistema tiene un orden total.

Una sola entidad no puede tener dos eventos 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 procesos, que es el tipo de orden que proporciona el reloj lógico de Lamport, entonces solo podemos decir el orden entre las entidades que interactúan. Lamport abordó el pedido de dos eventos con la misma marca de tiempo (o contador): "Para romper los empates, usamos cualquier orden total arbitrario de los procesos". ^[2] Por lo tanto, dos marcas de tiempo o contadores pueden ser iguales dentro de un sistema distribuido, pero al aplicar el algoritmo de relojes lógicos, los eventos que ocurren siempre mantendrán al menos un orden parcial estricto. $<$

Los relojes Lamport conducen a una situación en la que todos los eventos de un sistema distribuido están totalmente ordenados. Es decir, si , entonces podemos decir que realmente sucedió antes . $a\rightarrow b$ $a$ $b$

Tenga en cuenta que con los relojes de Lamport, no se puede decir nada sobre la hora real de y . Si el reloj lógico dice , eso no significa en realidad que sucedió antes en términos de tiempo real. $a$ $b$ $C(a)<C(b)$ $a$ $b$

Los relojes Lamport muestran no causalidad, pero no capturan toda la causalidad. El conocimiento y los espectáculos no causaron o pero no podemos decir cuál inició . $a\rightarrow c$ $b\rightarrow c$ $c$ $a$ $b$ $c$

Este tipo de información puede ser importante cuando se intenta reproducir eventos en un sistema distribuido (como cuando se intenta recuperar después de un bloqueo). Si un nodo se cae y conocemos las relaciones causales entre los mensajes, entonces podemos reproducir esos mensajes y respetar la relación causal para que ese nodo vuelva al estado en el que debe estar. ^[3]

Referencias

^ "3ª edición de sistemas distribuidos (2017)" . DISTRIBUTED-SYSTEMS.NET . Consultado el 20 de marzo de 2021 .
↑ ^a ^b Lamport, L. (1978). "Hora, relojes y ordenamiento de eventos en un sistema distribuido" (PDF) . Comunicaciones de la ACM . 21 (7): 558–565. doi : 10.1145 / 359545.359563 .
^ "Relojes y sincronización - documentación alfa de sistemas distribuidos" . books.cs.luc.edu . Consultado el 13 de diciembre de 2017 .

Ver también

[1] "3ª edición de sistemas distribuidos (2017)" . DISTRIBUTED-SYSTEMS.NET . Consultado el 20 de marzo de 2021 .

[Lamport_1978-2] Lamport, L. (1978). "Hora, relojes y ordenamiento de eventos en un sistema distribuido" (PDF) . Comunicaciones de la ACM . 21 (7): 558–565. doi : 10.1145 / 359545.359563 .

[3] "Relojes y sincronización - documentación alfa de sistemas distribuidos" . books.cs.luc.edu . Consultado el 13 de diciembre de 2017 .

[1]