Detección de terminación

Asumimos el siguiente modelo del sistema distribuido:

• El sistema es fiable, es decir, ni los procesos/procesadores no 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 están iniciados por un proceso ya trabajando.

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

• se manda mensajes para realizar las tareas del programa
• si un proceso recibe un mensaje lo tiene que procesar
• se manda señales para realizar la detección de terminación
• cuando un proceso se ha decido terminar (sea la razón que sea) no manda más mensajes a los demás, sin embargo, si recibe de nuevo un mensaje reanuda el trabajo
• los canales para los mensajes y los señales existen siempre en pares y los canales de los 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 raro considerando los muchos problemas que se puede solucionar con estrategias de divide-y-vencerás.

La detección de 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 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 desea terminar un proceso manda 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 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, manda señales según los valores déficit de todas sus arista 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 como en el caso del árbol sencillo.