Algoritmo de Chandy-Lamport

El algoritmo Chandy-Lamport es un algoritmo de instantánea que se utiliza en sistemas distribuidos para registrar un estado global coherente de un sistema asíncrono. Fue desarrollado y nombrado en honor a Leslie Lamport y K. Mani Chandy.

Historia

Según el sitio web de Leslie Lamport, "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 habíamos bebido demasiado vino para pensar en ello en ese momento. A la mañana siguiente, en la ducha, se me ocurrió la solución. Cuando llegué a la oficina de Chandy, me estaba esperando con la misma solución”.

Definición

Las suposiciones del algoritmo son las siguientes:

• No hay fallas y todos los mensajes llegan intactos y sólo una vez
• Los canales de comunicación son unidireccionales y se ordena FIFO
• Hay una vía de comunicación entre los dos procesos del sistema
• Cualquier proceso puede iniciar el algoritmo de instantáneas
• El algoritmo de instantánea no interfiere con la ejecución normal de los procesos
• Cada proceso en el sistema registra su estado local y el estado de sus canales entrantes

El algoritmo funciona usando mensajes de marcador. Cada proceso que quiere iniciar una instantánea registra su estado local y envía un marcador en cada uno de sus canales salientes. Todos los demás procesos, al recibir un marcador, registran su estado local, el estado del canal del que acaba de salir el marcador como vacío y envían mensajes de marcador en todos sus canales salientes. Si un proceso recibe un marcador después de haber registrado su estado local, registra el estado del canal de entrada del que provino el marcador como portador de todos los mensajes recibidos desde que registró por primera vez su estado local.

Algunas de las suposiciones del algoritmo se pueden facilitar usando un protocolo de comunicación más confiable como TCP/IP. El algoritmo se puede adaptar para que puedan ocurrir varias instantáneas simultáneamente.

Algoritmo

El algoritmo de Chandy-Lamport funciona así:

1. El proceso de observación (el proceso que toma una instantánea):
   1. Salva su propio estado local
   2. Envía un mensaje de solicitud de instantáneas con un token de instantáneas a todos los demás procesos
2. Un proceso que recibe el token de instantáneas por primera vez on cualquiera Mensaje:
   1. Envía al observador proceso su propio estado salvado
   2. Adjunta el token de instantáneas a todos los mensajes posteriores (para ayudar a propagar el token de instantáneas)
3. Cuando un proceso que ya ha recibido el token de instantáneas recibe un mensaje que no lleva el token de instantáneas, este proceso transmitirá ese mensaje al proceso de observador. Este mensaje fue enviado obviamente antes de la instantánea “cortada” (como no lleva un token de instantáneas y por lo tanto debe haber venido de antes de que el token de instantáneas fuera) y necesita ser incluido en la instantánea.

A partir de esto, el observador crea una instantánea completa: se guarda un estado guardado para cada proceso y todos los mensajes "en el éter".