algoritmo Dijkstra-Scholten - Dijkstra–Scholten algorithm
O algoritmo Dijkstra-Scholten (chamado após Edsger Dijkstra e Carel S. Scholten ) é um algoritmo para a detecção de terminação num sistema distribuído . O algoritmo foi proposto por Dijkstra e Scholten em 1980.
Primeiro, vamos considerar o caso de um simples gráfico do processo , que é uma árvore . A computação distribuída que é estruturado em árvore não é incomum. Um tal gráfico processo pode surgir quando o cálculo é estritamente uma divisão e conquista tipo. Um nó inicia o cálculo e divide o problema em duas (ou mais, geralmente um múltiplo de duas) partes aproximadamente iguais e distribuir essas partes para outros processadores. Este processo continua de forma recursiva até que os problemas são de tamanho suficientemente pequeno para resolver num único processador.
Conteúdo
Algoritmo
O algoritmo Dijkstra-Scholten é um algoritmo baseado em árvore que pode ser descrito pelo seguinte:
- O iniciador de um cálculo é a raiz da árvore.
- Ao receber uma mensagem computacional:
- Se o processo de recebimento não está neste momento na computação: o processo se junta a árvore, tornando-se uma criança do remetente da mensagem. (Nenhuma mensagem de confirmação é enviada neste momento.)
- Se o processo de recebimento já está na computação: o processo imediatamente envia uma mensagem de confirmação para o remetente da mensagem.
- Quando um processo não tem mais filhos e se tornou ocioso, o processo desprende-se da árvore, enviando uma mensagem de reconhecimento a seu pai árvore.
- Rescisão ocorre quando o iniciador não tem filhos e se tornou ocioso.
algoritmo Dijkstra-Scholten para uma árvore
- Para uma árvore, é fácil de detectar terminação. Quando um processo folha determina que ele terminou, ele envia um sinal para seu pai. Em geral, um processo espera por todos os seus filhos para enviar sinais e, em seguida, envia um sinal para seu pai.
- O programa termina quando a raiz recebe sinais de todos os seus filhos.
algoritmo Dijkstra-Scholten para grafos acíclicos dirigidos
- O algoritmo para uma árvore pode ser estendido para acíclicos grafos dirigidos. Nós adicionamos um défice atributo inteiro adicional para cada aresta.
- Em uma borda de entrada, Déficit denotará a diferença entre o número de mensagens recebidas e o número de sinais enviados em resposta.
- Quando um nó deseja terminar, ele aguarda até que tenha recebido sinais de bordas de saída reduzindo seus déficits a zero.
- Em seguida, ele envia sinais suficientes para assegurar que o défice é zero em cada borda de entrada.
- Como o gráfico é acíclico, alguns nós não terá bordas de saída e esses nós será o primeiro a terminar depois de enviar sinais suficientes para suas bordas de entrada. Depois que os nós de nível superior irá terminar nível por nível.
algoritmo Dijkstra-Scholten para cíclicos dirigido gráficos
- Se os ciclos são permitidos, o algoritmo anterior não funciona. Isto é porque, pode não haver qualquer nó com zero bordas de saída. Então, potencialmente existe nenhum nó que pode terminar sem consultar outros nós.
- O algoritmo Dijkstra-Scholten resolve este problema criando implicitamente uma árvore de expansão do gráfico. A-árvore de expansão é uma árvore, que inclui cada um nó do gráfico subjacente uma vez e a borda-conjunto é um subconjunto do conjunto original de arestas.
- A árvore vai ser dirigido (ou seja, os canais será dirigido) com o nó-origem (que inicia o cálculo) como a raiz.
- A-árvore de expansão é criado da seguinte maneira. Uma variável First_Edge é adicionado a cada nó. Quando um nó recebe uma mensagem para a primeira vez, que inicializa First_Edge com a extremidade através da qual se recebeu a mensagem. First_Edge nunca é alterado depois. Note-se que, a árvore de expansão não é única e depende da ordem de mensagens no sistema.
- A terminação é manipulado por cada nó em três etapas:
- Enviar sinais sobre todas as arestas de entrada, excepto a primeira borda. (Cada nó irá emitir sinais que reduz o défice em cada extremidade de entrada de zero.)
- Esperar por sinais a partir de todas as bordas de saída. (O número de sinais recebidos em cada extremidade de saída deve reduzir cada uma das suas défices a zero).
- Enviar sinais sobre First_Edge . (Uma vez que as etapas 1 e 2 são completos, um nó informa seu pai na árvore de expansão da sua intenção de encerrar.)