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
- Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introdução à Programação Distribuída Confiável e Segura (2. ed.), Springer, ISBN 978-3-642-15259-7
- C. Rodríguez, M. Villagra e B. Barán, algoritmos de equipe assíncrona para a satisfação booleana , Bionetics2007, pp. 66–69, 2007.
links externos
- Mídia relacionada a algoritmos distribuídos no Wikimedia Commons
- MIT Open Courseware - Distributed Algorithms