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 ordenamiento parcial de los eventos con una sobrecarga mínima y, conceptualmente, proporcionar un punto de partida para el método de reloj vectorial más avanzado . El algoritmo recibe su nombre de su creador, Leslie Lamport .
Los algoritmos distribuidos, como la sincronización de recursos, a menudo dependen de algún método para 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, un 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 un retraso de tiempo que hace que el disco reciba ambos mensajes al mismo tiempo, puede determinar qué mensaje sucedió antes que el otro: sucede antes si se puede llegar de a mediante una secuencia de movimientos de dos tipos: avanzar mientras se permanece 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. Nótese 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]
Lamport inventó un mecanismo simple mediante el cual se puede capturar numéricamente el orden que ocurrió antes . Un reloj lógico de Lamport es un valor numérico de contador de software que se mantiene en cada proceso.
En términos conceptuales, este reloj lógico puede considerarse como un reloj que solo tiene significado en relación con los mensajes que se transmiten entre procesos. Cuando un proceso recibe un mensaje, vuelve a sincronizar su reloj lógico con el del remitente. El reloj vectorial mencionado anteriormente es una generalización de la idea en el contexto de un número arbitrario de procesos paralelos e independientes.
El algoritmo sigue algunas reglas simples:
En pseudocódigo , el algoritmo para enviar es:
# se conoce el eventotiempo = tiempo + 1;# evento sucedeenviar(mensaje,hora);
El algoritmo para recibir un mensaje es:
(mensaje, marca de tiempo) = recibir();tiempo = max(marca de tiempo, tiempo) + 1;
Por cada dos eventos diferentes y que ocurren en el mismo proceso, y siendo la marca de tiempo para un determinado evento , es necesario que nunca sea igual a .
Por lo tanto es necesario que:
Para dos eventos cualesquiera, y , si hay alguna manera en que esto podría haber influido en , 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 de los que no podemos decir cuál ocurrió primero; cuando eso sucede, significa que no podrían haberse afectado entre sí. Si y no pueden tener ningún efecto entre sí, entonces no importa cuál ocurrió primero.
Se puede utilizar un reloj Lamport para crear un ordenamiento parcial de eventos entre procesos. Dado un reloj lógico que siga estas reglas, la siguiente relación es verdadera: si entonces , donde significa que sucedió antes .
Esta relación sólo funciona en un sentido y se denomina condición de consistencia del reloj : si un evento ocurre antes que otro, entonces el reloj lógico de ese evento ocurre antes que el del otro. La condición de consistencia fuerte del reloj , que es bidireccional (si entonces ), se puede obtener mediante otras técnicas, como los relojes vectoriales. Si se utiliza únicamente un reloj Lamport simple, sólo se puede inferir un orden causal parcial a partir del reloj.
Sin embargo, por la contraposición , es cierto que implica . Así, por ejemplo, si entonces no puede haber sucedido antes de .
Otra forma de decirlo es que significa que pudo haber sucedido antes de , o ser incomparable con el orden de sucedido antes de , pero no sucedió después de .
Sin embargo, las marcas de tiempo de Lamport se pueden utilizar para crear un ordenamiento total de eventos en un sistema distribuido mediante el uso de algún mecanismo arbitrario para deshacer los empates (por ejemplo, el identificador del proceso). La salvedad es que este ordenamiento es artificial y no se puede depender de él para implicar una relación causal.
En un sistema distribuido, en la práctica no es posible sincronizar el tiempo entre entidades (normalmente consideradas como procesos) dentro del sistema; por lo tanto, las entidades pueden utilizar el concepto de un reloj lógico basado en los eventos a través de los cuales se comunican.
Si dos entidades no intercambian ningún mensaje, entonces probablemente no necesitan compartir un reloj común; los eventos que ocurren en esas entidades se denominan eventos concurrentes.
Entre los procesos de la misma máquina local podemos ordenar los eventos en función del reloj local del sistema.
Cuando dos entidades se comunican mediante el paso de mensajes, se dice que el evento de envío ocurre antes que el evento de recepción, y se puede establecer el orden lógico entre los eventos.
Se dice que un sistema distribuido tiene un orden parcial si se puede establecer una relación de orden parcial entre los eventos del sistema. Si se puede establecer una "totalidad", es decir, una relación causal entre todos los eventos del sistema, entonces se dice que el sistema tiene un orden total.
Una sola entidad no puede tener dos eventos que ocurran 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 tipo de orden que proporciona el reloj lógico de Lamport, entonces solo podemos determinar el orden entre las entidades que interactúan. Lamport abordó el ordenamiento de dos eventos con la misma marca de tiempo (o contador): "Para desempatar, 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 de Lamport conducen a una situación en la que todos los eventos en un sistema distribuido están totalmente ordenados. Es decir, si , entonces podemos decir que en realidad sucedió antes de .
Obsérvese que con los relojes de Lamport no se puede decir nada sobre el tiempo real de y . Si el reloj lógico dice , eso no significa en realidad que eso haya sucedido antes en términos de tiempo real.
Los relojes de Lamport muestran la no causalidad, pero no captan toda la causalidad. Saber y muestra que no causó o no, pero no podemos decir cuál lo inició .
Este tipo de información puede ser importante cuando se intenta reproducir eventos en un sistema distribuido (por ejemplo, cuando se intenta recuperarse después de una falla). Si un nodo se cae y conocemos las relaciones causales entre los mensajes, podemos reproducir esos mensajes y respetar la relación causal para que ese nodo vuelva al estado en el que debe estar. [3]
La relación de lo que sucedió antes captura la causalidad potencial, no la causalidad verdadera. En 2011-12, Munindar Singh propuso un enfoque declarativo de múltiples agentes basado en la causalidad verdadera llamado protocolos de información. Un protocolo de información especifica las restricciones de las comunicaciones entre los agentes que constituyen un sistema distribuido. [4] Sin embargo, en lugar de especificar el orden de los mensajes (por ejemplo, a través de una máquina de estados, una forma común de representar protocolos en informática), un protocolo de información especifica las dependencias de información entre las comunicaciones que los agentes (los puntos finales del protocolo) pueden enviar. Un agente puede enviar una comunicación en un estado local (su historial de comunicaciones) solo si la comunicación y el estado juntos satisfacen las dependencias de información relevantes. Por ejemplo, un protocolo de información para una aplicación de comercio electrónico puede especificar que para enviar una cotización con parámetros ID (un uniquificador), artículo y precio, el vendedor ya debe conocer el ID y el artículo de su estado, pero puede generar cualquier precio que desee. Una cosa notable acerca de los protocolos de información es que, aunque las emisiones están restringidas, las recepciones no lo están. En concreto, los agentes pueden recibir comunicaciones en cualquier orden: las recepciones simplemente llevan información y no tiene sentido retrasarlas. Esto significa que los protocolos de información pueden implementarse en servicios de comunicación desordenados como UDP .
La idea más amplia es la de la semántica de aplicaciones, la idea de diseñar sistemas distribuidos basados en el contenido de los mensajes, una idea implicada en el principio de extremo a extremo . Los enfoques actuales ignoran en gran medida la semántica y se centran en proporcionar garantías de orden y entrega de mensajes independientes de la aplicación ("sintácticas") en los servicios de comunicación, que es donde ayudan ideas como la causalidad potencial. Pero si tuviéramos una forma adecuada de hacer semántica de aplicaciones, entonces no necesitaríamos tales servicios de comunicación. Un servicio de comunicación desordenado y poco fiable sería suficiente. El valor real del enfoque de los protocolos de información es que proporciona las bases para un enfoque de semántica de aplicaciones.
