Lamport

Algoritmo de Lamport

Para sincronizar los relojes lógicos, Lamport definió una relación llamada ocurre antes de. La expresión a  b se lee: "a ocurre antes de b” e indica que todos los procesoscoinciden en que primero ocurre el evento a y después el evento b. La relación "ocurre antes de" se puede observar de manera directa en dos situaciones:
1. Si a y b son eventos en el mismo proceso y aocurre antes de b, entonces a b es verdadero.
2. Si a es el evento del envío de un mensaje por un proceso y b es el evento de la recepción del mensaje por otro proceso, entonces a  b también esverdadero. Un mensaje no se puede recibir antes de ser enviado o al mismo tiempo en que se envía, puesto que tarda en llegar una cantidad finita de tiempo.
"Ocurre antes de" es una relación transitiva,de modo que si a  b y b  c, entonces a  c. Si dos eventos, x y y, están en procesos diferentes que no intercambian mensajes, entonces xy no es verdadero, ni tampoco lo es y  x. Se dice que estoseventos son concurrentes, lo que significa que nada se puede decir (o se necesita decir) acerca del momento en el que ocurren o cuál de ellos es el primero.
Lo que necesitamos es una forma de medirel 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. Estos valores del tiempo deben tener la propiedad de que si a  b ,entonces C(a) < C(b). En otros términos, si a y b son dos procesos dentro del mismo evento y a ocurre antes de b, entonces C(a) < C(b). De manera análoga, si a es el envío de un mensaje por un proceso y bla recepción de ese mensaje por otro proceso, entonces C(a) y C(b) deben ser asignados de tal forma que todos estén de acuerdo en los valores de C(a) y C(b) con C(a) < C(b). Además, el tiempo delreloj, C, siempre debe ir hacia adelante (creciente), y nunca hacia atrás (decreciente). Se pueden hacer correcciones al tiempo al sumar un valor positivo al reloj, pero nunca se le debe restar un valor...