Algoritmo de Chandy-Lamport

El algoritmo de Chandy-Lamport es un algoritmo de instantáneas para sistemas asíncronos desarrollado por Leslie Lamport y K. Mani Chandy.

El algoritmo de Chandy-Lamport se utiliza en sistemas distribuidos con el objetivo de obtener una instantánea (conjunto de estados de proceso y canal de comunicación) global y consistente para registrarlo como un estado global consistente. El estado global se construye a partir de la iniciativa de un proceso cualquiera del sistema distribuido (iniciador). El mismo Leslie Lamport recoge en su página web cómo surgió la idea, citando textualmente en su página web personal: "El algoritmo de instantáneas distribuidas que se describe aquí surgió cuando visité a Chandy, que entonces estaba en la Universidad de Texas en Austin. Me planteó el problema durante la cena, pero ambos tuvimos demasiado vino para pensarlo en ese momento. A la mañana siguiente, en la ducha, se me ocurrió la solución. Cuando llegué a la oficina de Chandy, él me estaba esperando con la misma solución."

Ante la imposibilidad de sincronizar perfectamente los relojes en un sistema distribuido, no se puede usar en ellos el tiempo físico para obtener el orden de cualquier suceso que ocurra. Para evitar este problema, Lamport sugiere la utilización de tiempos lógicos para conseguir sincronización. El objetivo es asociar a todos los sucesos una marca de tiempo independiente del reloj físico y poder ordenarlos mediante relaciones “ocurre antes que”. Con tiempos lógicos, si a sucede antes que b, el reloj es menor, pero si el reloj de a es menor que el de b, no implica que a haya ocurrido antes que b. Los relojes vectoriales sí consiguen hacer ciertas ambas suposiciones. Un reloj vectorial para un sistema de N procesos es un vector de N enteros. Cada proceso mantiene su propio reloj vectorial Vi, donde coloca sus propias marcas de tiempo de sus sucesos locales. Para compartirlos, existen 4 reglas básicas para actualizar los relojes:

Un estado global consistente es aquel que corresponde con un corte consistente. Podemos caracterizar la ejecución de un sistema distribuido como una serie de transacciones entre los estados globales del sistema: s0-s1-s2-s3…

Corte consistente: si el evento de recepción de un mensaje está “dentro” del corte, entonces el evento de envío de dicho mensaje también debe estar. Un corte c es consistente si, para cada suceso que contiene, también contiene todos los sucesos que “sucedieron antes que”.

Corte consistente para relojes lógicos vectoriales: Un corte c es consistente si, para cada proceso P, su reloj lógico en ese momento es mayor o igual que los valores que tienen almacenados el resto de procesos del reloj de P.

El algoritmo supone que:

El algoritmo utiliza mensajes especiales, llamados ‘mark’, que son distintos a todo el resto de mensajes en el sistema durante su ejecución normal. Estos ´mark´ tienen doble funcionalidad: como aviso para que el receptor guarde su propio estado si no lo ha hecho aún, y como un medio para decidir qué mensajes incluir en el estado del canal.

Pseudocódigo basado en la diferenciación de dos reglas principales: 1) Regla de recepción del mark para el proceso Pi por el canal C:

2) Regla de envío del mark para el proceso Pi:

El algoritmo de instantánea selecciona un corte de la historia de la ejecución. El corte, y por tanto, el estado global buscado, es consistente. Para ejemplificar esta afirmación: Sean si y sj sucesos que ocurren en pi y pj respectivamente, tal que si->sj. Afirmamos que si sj está en el corte entonces si también lo está. Esto es, si sj sucedió antes de que pj registrara su estado, entonces si debe haber sucedido antes de que pi registrara el suyo.

---