Actividad 5 - Algoritmo Distribuido

Una subclase de los algoritmos paralelos, los algoritmos distribuidos son algoritmos diseñados para trabajar en entornos tipo clusters y de computación distribuida, donde se usan otras técnicas, fuera del alcance de los algoritmos paralelos clásicos.

Estado Global

Estado global: estado local de cada proceso + estado de cada canal.

Estado de cada proceso: sólo las variables que nos interesen.

Estado de cada canal: mensajes enviados y todavía no entregados.

• Usos del estado global: 
• Detección de terminación.
• Depuración distribuida.

Algoritmo de Chandy-Lamport

El algoritmo de Chandy y Lamport, bajo determinadas suposiciones, permite determinar el estado global de un sistema distribuido

Conceptos previos

Una instantánea distribuida refleja el estado que pudo haberse alcanzado en el sistema.
Las instantáneas reflejan sólo estados consistentes.
Si el estado de P, dice que P ha recibido un mensaje de Q, en la instantánea, Q envió antes un mensaje a P.
La noción de estado global se refleja por el concepto de corte.

• Cualquier proceso inicia el algoritmo.
• Sea P el proceso iniciador.
• P guarda su estado local, luego envía un mensaje de marca a todos los demás procesos.
• Cuando un proceso recibe el mensaje de marca:
• Si no ha guardado su estado local: guarda su estado local y envía marca a todos los demás procesos. A partir de este momento almacenará lo que llegue por los canales entrantes.
• Si ha guardado su estado local, guarda los mensajes recibidos por el canal (desde que el proceso guardó su estado local, hasta que recibió marca por este canal).
• Un proceso termina, cuando ha recibido marca por todos los canales.
• Cuando termina, envía su estado y el de sus canales al iniciador.