El algoritmo Chandy-Lamport es un algoritmo de instantáneas que se utiliza en sistemas distribuidos para registrar un estado global consistente de un sistema asincrónico . Fue desarrollado por Leslie Lamport y K. Mani Chandy y recibió su nombre en honor a ellos . [1]
Según el sitio web de Leslie Lamport, el algoritmo de la instantánea fue descrito cuando visitaron a Chandy, que estaba en la Universidad de Texas (Austin) . Planteó el problema durante la cena, pero habían bebido demasiado vino como para pensar en ello. A la mañana siguiente, mientras Lamport se duchaba, se le ocurrió la solución. Cuando llegó a la oficina de Chandy, lo estaba esperando con la misma solución. Consideraron que el algoritmo era la aplicación directa de las ideas básicas del artículo 27, titulado " Tiempo, relojes y ordenación de eventos en un sistema distribuido". [2]
Los supuestos del algoritmo son los siguientes:
El algoritmo funciona mediante mensajes de marcadores. Cada proceso que desea iniciar una instantánea registra su estado local y envía un marcador en cada uno de sus canales de salida. Todos los demás procesos, al recibir un marcador, registran su estado local, el estado del canal del que acaba de llegar el marcador como vacío, y envían mensajes de marcadores en todos sus canales de salida. Si un proceso recibe un marcador después de haber registrado su estado local, registra el estado del canal de entrada del que procede 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 utilizando un protocolo de comunicación más confiable como TCP/IP . El algoritmo se puede adaptar para que se puedan producir múltiples instantáneas simultáneamente.
El algoritmo de Chandy-Lamport funciona así:
A partir de esto, el observador construye una instantánea completa: se guarda un estado para cada proceso y se guardan todos los mensajes “en el éter”.