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, considere el caso de un gráfico de proceso simple que es un árbol . Un cálculo distribuido que tiene una estructura de árbol no es poco común. Un gráfico de proceso de este tipo puede surgir cuando el cálculo es estrictamente del tipo divide y vencerás . Un nodo inicia el cálculo y divide el problema en dos partes aproximadamente iguales (o más, generalmente un múltiplo de 2) y distribuye esas partes a otros procesadores. Este proceso continúa recursivamente hasta que los problemas son de un tamaño suficientemente pequeño para resolverlos en un solo procesador.

Algoritmo

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 se encuentra actualmente en el cálculo: el proceso se une al árbol convirtiéndose en un hijo del remitente del mensaje. (No se envía ningún mensaje de confirmación en este punto).
  • Si el proceso receptor ya está en el cálculo: el proceso envía inmediatamente un mensaje de reconocimiento al remitente del mensaje.
• Cuando un proceso no tiene más hijos y queda inactivo, el proceso se separa del árbol enviando un mensaje de reconocimiento a su árbol padre.
• La terminación ocurre cuando el iniciador no tiene hijos y queda inactivo.

Algoritmo de Dijkstra-Scholten para un árbol

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

Algoritmo de Dijkstra-Scholten para grafos acíclicos dirigidos

• El algoritmo para un árbol se puede extender a gráficos dirigidos acíclicos. Agregamos un atributo entero adicional, Déficit, a cada arista.
• En un borde entrante, Déficit denotará la diferencia entre el número de mensajes recibidos y el número de señales enviadas en respuesta.
• Cuando un nodo desea terminar, espera hasta recibir señales de los bordes salientes, reduciendo sus déficits a cero.
• Luego envía suficientes señales para garantizar que el déficit sea cero en cada borde entrante.
• Como el gráfico es acíclico, algunos nodos no tendrán aristas salientes y estos nodos serán los primeros en terminar después de enviar suficientes señales a sus aristas entrantes. Después de eso, los nodos de niveles superiores terminarán nivel por nivel.

Algoritmo de Dijkstra-Scholten para grafos cíclicos dirigidos

• Si se permiten ciclos, el algoritmo anterior no funciona. Esto se debe a que puede que no haya 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 vez y el conjunto de aristas es un subconjunto del conjunto original de aristas.
• El árbol será dirigido (es decir, los canales serán dirigidos) con el nodo de origen (que inicia el cálculo) como raíz.
• El árbol de expansión se crea de la siguiente manera. Se agrega una variable First_Edge a cada nodo. Cuando un nodo recibe un mensaje por primera vez, inicializa First_Edge con el borde a través del cual recibió el mensaje. First_Edge nunca se modifica posteriormente. Tenga en cuenta que el árbol de expansión no es único y depende del orden de los mensajes en el sistema.
• La terminación la gestiona cada nodo en tres pasos:
  1. Envía señales en todos los bordes entrantes excepto el primero. (Cada nodo enviará señales que reducen el déficit en cada borde entrante a cero).
  2. Espere señales de todos los bordes salientes. (La cantidad de señales recibidas en cada borde saliente debería reducir cada uno de sus déficits a cero).
  3. Envía señales en 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).

Véase también

• Algoritmo de Huang

Referencias

1. Ghosh, Sukumar (2010), "9.3.1 El algoritmo de Dijkstra–Scholten", Sistemas distribuidos: un enfoque algorítmico, CRC Press, págs. 140-143, ISBN 9781420010848.
2. Fokkink, Wan (2013), "Algoritmo 6.1 de Dijkstra-Scholten", Algoritmos distribuidos: un enfoque intuitivo, MIT Press, págs. 38-39, ISBN 9780262318952.
3. Dijkstra, Edsger W.; Scholten, CS (1980), "Detección de terminación para cálculos difusos" (PDF) , Information Processing Letters , 11 (1): 1–4, doi :10.1016/0020-0190(80)90021-6, MR  0585394.