Detección de terminación

Asumimos el siguiente modelo de sistema distribuido:

• El sistema es fiable, es decir, ni los procesos/procesadores ni el sistema de comunicación provocan fallos.
• Los procesos que están conectados usan un canal bidireccional para intercambiar mensajes.
• Existe un único proceso que inicia la computación; todos los demás procesos son iniciados por un proceso ya iniciado.

Para detectar la terminación de todos los procesos acordamos lo siguiente:

• se envían mensajes para realizar las tareas del programa
• si un proceso recibe un mensaje lo tiene que procesar
• se envían señales para realizar la detección de terminación
• cuando se decide la terminación de un proceso (por la razón que sea) no envía más mensajes a los demás, sin embargo, si recibe de nuevo un mensaje reanuda el trabajo
• los canales para los mensajes y las señales existen siempre en pares y los canales de las señales siempre funcionan independiente del estado del proceso o del estado del canal de mensajes

Un ejemplo para la detección de terminación es el algoritmo de Dijkstra-Scholten.

Asumimos primero que el grafo de los procesos (es decir, el grafo que se establece por los intercambios de mensajes entre los procesos) forme un árbol. Esta situación no es tan rara considerando los muchos problemas que se pueden solucionar con estrategias tipo divide-y-vencerás.

La detección de la terminación resulta fácil: una hija en el arbol manda y su madre que ha terminado cuando haya recibido el mismo mensaje de todas sus hijas y cuando se ha decido terminar también.

El programa termina cuando la raíz del árbol ha terminado, es decir, cuando ha recibido todas las señales de terminación de todas sus hijas y no queda nada más por hacer. La raíz propaga la decisión de que todos pueden terminar definitivamente a lo largo del árbol.

Ampliamos el algoritmo para que funcione también con grafos acíclicos. Añadimos a cada arista un campo ``déficit'' que se aumenta siempre que se haya pasado un mensaje entre los procesos a ambos lados de la arista. Cuando se desea terminar un proceso, se envían por todas sus aristas entrantes tantas señales como indica el valor ``déficit'' disminuendo así el campo. Un proceso puede terminar cuando desea terminar y todos sus aristas salientes tengan déficit cero.

El algoritmo de Dijkstra-Scholten desarrollado hasta ahora obviamente no funciona para grafos que contienen cíclos. Sin embargo, se puede usar el siguiente truco:

Siempre y cuando un proceso es iniciado por primera vez, el correspondiente mensaje causa una arista nueva en el grafo que es la primera que conecta a dicho proceso. Si marcamos estas aristas especialmente, se observa que forman un árbol abarcador (spanning tree) del grafo.

El algoritmo de determinación de terminación procede entonces como sigue:

• cuando un proceso decide terminar, envía señales según los valores déficit de todas sus aristas entrantes menos de las aristas que forman parte del árbol abarcador.
• una vez obtenido todos los déficits (menos los del árbol) igual a cero, se procede igual que en el caso del árbol sencillo.