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."

Consideraciones Previas

Tiempos lógicos y Relojes vectoriales

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:

• RV1: Inicialmente Vi[j]=0 para j=1, 2, …, N.
• RV2: Antes de que ocurra un evento en Pi: Vi[i]=Vi[i]+1.
• RV3: Pi incluye el timestamp t=Vi en cada mensaje que envía.
• RV4: Cuando Pi tiene un evento de recepción con timestamp t, Vi[j]=max(Vi[j], t[j]) para j=1,2,…,N.

Estado global y cortes consistentes

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.

Precondiciones

El algoritmo supone que:

• No fallan ni los canales ni los procesos: la comunicación es fiable por lo que todos los mensajes se reciben intactos y una única vez.
• Los canales son unidireccionales con entrega de tipo FIFO.
• El grafo de los procesos y canales está fuertemente conectado, hay canal de comunicación directa entre todos los estados.
• Cualquier proceso puede tomar una instantánea global en cualquier instante.
• Mientras tiene lugar una instantánea los procesos pueden continuar su ejecución y comunicación.

El algoritmo

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:

  Si (Pi no ha registrado su estado todavía)
     Registra su estado de proceso ahora;
     Registra el estado del canal C como vacío;
     Activa el registro de mensajes que lleguen por otros canales 
     entrantes;
  Sino
     Pi registra el estado de c como el conjunto de mensajes que ha 
     recibido 
     sobre c desde que guardó su estado (mensajes posteriores a la 
     instantánea).
  FinSi

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

  Después de registrar su propio estado, para canal de salida de C, Pi 
  envía un mensaje de instantánea por el canal c

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.

Ejemplo

Ejemplo grafico Chandy-Lamport

En un sistema distribuido en el que hay tres procesos, etiquetados como A, B, C, y se quiere registrar las interacciones de mensajes entre ellos. Cada proceso tiene su propio vector de tiempo local con tres componentes.

La siguiente imagen muestra un diagrama de los tres procesos y las comunicaciones entre ellos:

1. En el evento 1, A realiza una operación local y su vector de tiempo local se actualiza a (1, 0, 0).
2. En el evento 2, B realiza una operación local y su vector de tiempo local se actualiza a (0, 1, 0).
3. En el evento 3, C realiza una operación local y su vector de tiempo local se actualiza a (0, 0, 1).
4. En el evento 4, A envía un mensaje al proceso B. El vector de A se incluye en el mensaje y se actualiza a (2, 0, 0) debido a la operación de envío. B recibe el mensaje, compara su vector (0, 1, 0) con el vector recibido (2, 0, 0) y actualiza su vector a (2, 1, 0).
5. En el evento 5, el proceso B envía un mensaje al proceso C. El vector de B se incluye en el mensaje y se actualiza a (2, 2, 0) debido a la operación de envío. El proceso C recibe el mensaje, compara su vector de tiempo local (0, 0, 1) con el vector recibido (2, 2, 0) y actualiza su vector a (2, 2, 1).

Tras todas estas operaciones, el resultado final de los vectores de tiempo local de los procesos es:

• A: (2, 0, 0) B: (2, 2, 0) C: (2, 2, 1)

Referencias

• Chandy, K. M., & Lamport, L. (1985). Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems (TOCS), 3(1), 63-75.[1] Archivado el 11 de mayo de 2018 en Wayback Machine.
• Tel, G. (2000). Introduction to Distributed Algorithms (2ª ed.). New York: Cambridge University Press.
• Coulouris, G. (2001). Sistemas distribuidos: Conceptos y diseños. (P. de la F. Redondo & C. L. Bello, Trads.) (Edición: 3). Madrid: ADDISON WESLEY.
• Rodrigo Santamaría. Apuntes Sistemas Distribuidos Universidad de Salamanca. | Tema 4 - Tiempos y Estados

• Datos: Q2247012