Algoritmo distribuído - Distributed algorithm

Um algoritmo distribuído é um algoritmo projetado para ser executado em hardware de computador construído a partir de processadores interconectados . Algoritmos distribuídos são usados ​​em diferentes áreas de aplicação da computação distribuída , como telecomunicações , computação científica , processamento de informações distribuídas e controle de processos em tempo real . Os problemas padrão resolvidos por algoritmos distribuídos incluem eleição de líder , consenso , pesquisa distribuída , geração de spanning tree , exclusão mútua e alocação de recursos .

Algoritmos distribuídos são um subtipo de algoritmo paralelo , normalmente executado simultaneamente , com partes separadas do algoritmo sendo executadas simultaneamente em processadores independentes e tendo informações limitadas sobre o que as outras partes do algoritmo estão fazendo. Um dos maiores desafios no desenvolvimento e implementação de algoritmos distribuídos é coordenar com sucesso o comportamento das partes independentes do algoritmo em face de falhas do processador e links de comunicação não confiáveis. A escolha de um algoritmo distribuído apropriado para resolver um determinado problema depende das características do problema e das características do sistema em que o algoritmo será executado, como o tipo e a probabilidade de falhas do processador ou do link, o tipo de comunicação entre processos que pode ser executado, e o nível de sincronização de tempo entre processos separados.

Problemas padrão

Commit atômico
Um commit atômico é uma operação em que um conjunto de mudanças distintas é aplicado como uma única operação. Se a confirmação atômica for bem-sucedida, significa que todas as alterações foram aplicadas. Se houver uma falha antes que o commit atômico possa ser concluído, o "commit" é abortado e nenhuma alteração será aplicada.
Os algoritmos para resolver o protocolo de confirmação atômica incluem o protocolo de confirmação de duas fases e o protocolo de confirmação de três fases .
Consenso
Algoritmos de consenso tentam resolver o problema de vários processos concordando em uma decisão comum.
Mais precisamente, um protocolo de consenso deve satisfazer as quatro propriedades formais abaixo.
  • Rescisão : todo processo correto decide algum valor.
  • Validade : se todos os processos propõem o mesmo valor , então todo processo correto decide .
  • Integridade : todo processo correto decide no máximo um valor, e se decide algum valor , então deve ter sido proposto por algum processo.
  • Acordo : se um processo correto decide , então todo processo correto decide .
Os algoritmos comuns para resolução de consenso são o algoritmo Paxos e o algoritmo Raft .
Pesquisa distribuída
Eleição de líder
A eleição do líder é o processo de designar um único processo como organizador de alguma tarefa distribuída entre vários computadores (nós). Antes de a tarefa ser iniciada, todos os nós da rede não sabem qual nó servirá como o "líder" ou coordenador da tarefa. Depois que um algoritmo de eleição de líder foi executado, no entanto, cada nó em toda a rede reconhece um nó particular e único como o líder da tarefa.
Exclusão mútua
Estruturas de dados sem bloqueio
Transmissão confiável
A transmissão confiável é uma comunicação primitiva em sistemas distribuídos. Uma transmissão confiável é definida pelas seguintes propriedades:
  • Validade - se um processo correto enviar uma mensagem, algum processo correto acabará por entregar essa mensagem.
  • Acordo - se um processo correto entrega uma mensagem, então todos os processos corretos eventualmente entregam essa mensagem.
  • Integridade - todo processo correto entrega a mesma mensagem no máximo uma vez e somente se essa mensagem tiver sido enviada por um processo.
Uma transmissão confiável pode ter ordenação sequencial, causal ou total.
Replicação
Alocação de recursos
Geração de Spanning Tree
Quebra de simetria, por exemplo, coloração de vértice

Referências

Leitura adicional

links externos