Algoritmo de Dijkstra-Scholten

El algoritmo de Dijkstra-Scholten (llamado así por Edsger W. Dijkstra y Carel S. Scholten ) es un algoritmo para detectar la terminación en un sistema distribuido . ^{[ 1 ] [ 2 ]} El algoritmo fue propuesto por Dijkstra y Scholten en 1980. ^{[ 3 ]}

En primer lugar, consideremos el caso de un grafo de procesos simple con estructura de árbol . Un cálculo distribuido con estructura de árbol es bastante común. Este tipo de grafo de procesos puede surgir cuando el cálculo es estrictamente de tipo divide y vencerás . Un nodo inicia el cálculo, divide el problema en dos partes aproximadamente iguales (o, más comúnmente, en un múltiplo de 2) y las distribuye a otros procesadores. Este proceso continúa recursivamente hasta que los problemas tienen un tamaño suficientemente pequeño como para ser resueltos por un solo procesador.

El algoritmo de Dijkstra-Scholten es un algoritmo basado en árboles que se puede describir de la siguiente manera:

• El iniciador de un cálculo es la raíz del árbol.
• Al recibir un mensaje computacional:
  • Si el proceso receptor no participa actualmente en el cálculo, se incorpora al árbol convirtiéndose en hijo del remitente del mensaje. (En este punto no se envía ningún mensaje de confirmación).
  • Si el proceso receptor ya está en el cálculo, envía inmediatamente un mensaje de confirmación al remitente del mensaje.
• Cuando un proceso ya no tiene hijos y se encuentra inactivo, se desvincula del árbol enviando un mensaje de confirmación a su proceso padre.
• La terminación se produce cuando el iniciador no tiene hijos y se encuentra inactivo.

• En un árbol, detectar la terminación es sencillo. Cuando un proceso hoja determina que ha terminado, envía una señal a su proceso padre. Generalmente, un proceso espera a que todos sus hijos envíen señales y luego envía una señal a su proceso padre.
• El programa finaliza cuando el proceso raíz recibe señales de todos sus procesos hijos.

• El algoritmo para un árbol se puede extender a grafos dirigidos acíclicos. Añadimos un atributo entero adicional, Déficit, a cada arista.
• En una conexión entrante, el Déficit indicará la diferencia entre el número de mensajes recibidos y el número de señales enviadas en respuesta.
• Cuando un nodo desea finalizar, espera hasta haber recibido señales de las aristas salientes que reduzcan sus déficits a cero.
• Luego, envía suficientes señales para asegurar que el déficit sea cero en cada flanco de entrada.
• Dado que el grafo es acíclico, algunos nodos no tendrán aristas salientes y serán los primeros en terminar tras enviar suficientes señales a sus aristas entrantes. Posteriormente, los nodos de niveles superiores terminarán nivel por nivel.

• Si se permiten ciclos, el algoritmo anterior no funciona. Esto se debe a que puede que no exista ningún nodo con cero aristas salientes. Por lo tanto, potencialmente no hay ningún nodo que pueda terminar sin consultar a otros nodos.
• El algoritmo de Dijkstra-Scholten resuelve este problema creando implícitamente un árbol de expansión del grafo. Un árbol de expansión es un árbol que incluye cada nodo del grafo subyacente una sola vez, y su conjunto de aristas es un subconjunto del conjunto original de aristas.
• El árbol estará dirigido (es decir, los canales estarán dirigidos) con el nodo fuente (que inicia el cálculo) como raíz.
• El árbol de expansión se crea de la siguiente manera: se añade una variable llamada First_Edge a cada nodo. Cuando un nodo recibe un mensaje por primera vez, inicializa First_Edge con la arista por la que recibió dicho mensaje. First_Edge no se modifica posteriormente. Cabe destacar que el árbol de expansión no es único y depende del orden en que se reciben los mensajes en el sistema.
• La terminación es gestionada por cada nodo en tres pasos  :
  1. Enviar señales a través de todas las aristas entrantes, excepto la primera. (Cada nodo enviará señales que reduzcan a cero el déficit en cada arista entrante).
  2. Espere a recibir señales de todas las aristas salientes. (El número de señales recibidas en cada arista saliente debería reducir a cero el déficit de cada una de ellas).
  3. Enviar señales a First_Edge . (Una vez completados los pasos 1 y 2, un nodo informa a su padre en el árbol de expansión sobre su intención de terminar).

• El algoritmo de Huang