El algoritmo Dijkstra – Scholten (llamado así por Edsger W. Dijkstra y Carel S. Scholten ) es un algoritmo para detectar terminación en un sistema distribuido . [1] [2] El algoritmo fue propuesto por Dijkstra y Scholten en 1980. [3]
Primero, considere el caso de un gráfico de proceso simple que es un árbol . Un cálculo distribuido que está estructurado en árbol no es infrecuente. 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 (o más, generalmente un múltiplo de 2) partes aproximadamente iguales y distribuye esas partes a otros procesadores. Este proceso continúa de forma recursiva hasta que los problemas son de 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 de recepción no está 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 momento).
- Si el proceso de recepción 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 está 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 se ha quedado inactivo.
Algoritmo de Dijkstra-Scholten para un árbol
- Para 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 termina cuando la raíz recibe señales de todos sus hijos.
Algoritmo de Dijkstra-Scholten para gráficos 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 borde.
- En un flanco 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 que haya recibido 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.
- Dado que el gráfico es acíclico, algunos nodos no tendrán bordes salientes y estos nodos serán los primeros en terminar después de enviar suficientes señales a sus bordes entrantes. Después de eso, los nodos en niveles superiores terminarán nivel por nivel.
Algoritmo de Dijkstra-Scholten para gráficos 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 bordes 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 gráfico. Un árbol de expansión es un árbol que incluye cada nodo del gráfico subyacente una vez y el conjunto de bordes es un subconjunto del conjunto de bordes original.
- El árbol será dirigido (es decir, los canales será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 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 cambia después. 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 es manejada por cada nodo en tres pasos:
- Envíe señales en todos los bordes entrantes excepto el primer borde. (Cada nodo enviará señales que reducen el déficit en cada borde entrante a cero).
- Espere las señales de todos los bordes salientes. (El número de señales recibidas en cada borde de salida debería reducir cada uno de sus déficits a cero).
- Envíe señales en First_Edge . (Una vez que se completan los pasos 1 y 2, un nodo informa a su padre en el árbol de expansión sobre su intención de terminar).
Ver también
Referencias
- ^ Ghosh, Sukumar (2010), "9.3.1 El algoritmo Dijkstra-Scholten", Sistemas distribuidos: un enfoque algorítmico , CRC Press, págs. 140-143, ISBN 9781420010848.
- ^ Fokkink, Wan (2013), "6.1 Algoritmo de Dijkstra-Scholten", Algoritmos distribuidos: un enfoque intuitivo , MIT Press, págs. 38–39, ISBN 9780262318952.
- ^ Dijkstra, Edsger W .; Scholten, CS (1980), "Detección de terminación para la difusión de cálculos" (PDF) , Cartas de procesamiento de información , 11 (1): 1–4, doi : 10.1016 / 0020-0190 (80) 90021-6 , MR 0585394.