CCT-UFCA/Ciência da Computação/Sistemas Distribuídos/Algoritmos Distribuídos

Conceitos e Características de Algoritmos Distribuídos

Um algoritmo distribuído é um conjunto de instruções que define como processos em diferentes nós de um sistema distribuído interagem para resolver problemas de forma cooperativa.

Características:
1. Descentralização:
  - Diferente de algoritmos centralizados, os distribuídos são projetados para funcionar sem um coordenador único.
2. Escalabilidade:
  - Capazes de funcionar eficientemente mesmo com o aumento do número de nós.
3. Tolerância a Falhas:
  - Precisam continuar funcionando mesmo quando alguns nós falham.
4. Coordenação e Consistência:
  - Garantem que os processos estejam sincronizados e que os dados sejam consistentes em todos os nós.
5. Latência de Comunicação:
  - A latência entre nós impacta o desempenho dos algoritmos.

Exemplo: Algoritmos de roteamento na internet, como o protocolo OSPF, são distribuídos para gerenciar rotas entre diferentes dispositivos.

Algoritmos de Difusão

Algoritmos de difusão são usados para disseminar informações de um nó para todos os outros em um sistema distribuído.

Tipos:
1. Difusão Inundada (Flooding):
  - Cada nó retransmite a mensagem para todos os vizinhos, até que todos os nós tenham recebido.
  - Vantagem: Simples e garante a entrega.
  - Desvantagem: Alta sobrecarga de mensagens.
2. Difusão Controlada:
  - Evita mensagens redundantes, usando contadores ou verificações de mensagens recebidas.

Exemplo: Protocolos de descoberta de rede, como ARP (Address Resolution Protocol), utilizam a difusão para localizar dispositivos.

Algoritmos de Consenso

Algoritmos de consenso permitem que múltiplos processos em um sistema distribuído concordem sobre um único valor ou estado, mesmo em presença de falhas.

Propriedades Fundamentais:

Confiabilidade: Todos os processos honestos concordam no mesmo valor.
Validade: O valor acordado deve ser válido, ou seja, proposto por um dos processos.
Tolerância a Falhas: Funcionam mesmo com falhas parciais (falhas bizantinas, por exemplo).

Algoritmos Famosos:

Paxos:
- Um algoritmo robusto e tolerante a falhas que garante consenso, amplamente usado em sistemas como bancos de dados distribuídos.

Exemplo: Usado pelo Google em seus sistemas distribuídos.

Raft:
- Simples de entender e implementar, usado em sistemas distribuídos como o etcd e Consul.

Exemplo : Gerenciamento de configuração de clusters de servidores.

Algoritmos de Consenso Bizantino:
- Lidam com nós maliciosos ou com comportamentos arbitrários.

Exemplo: O algoritmo utilizado pelo protocolo blockchain Ethereum.

Algoritmos de Replicação de Dados

Garantem que os dados sejam copiados e armazenados em múltiplos nós, mantendo consistência e disponibilidade.

Características:
- Replicação Forte: Garante que todos os nós tenham os mesmos dados a qualquer momento.
- Replicação Eventual: Eventualmente, todos os nós terão os mesmos dados, mas não imediatamente.
Exemplo de Técnicas:
1. Quórum de Leitura/Escrita:
  - Um subconjunto mínimo de nós é consultado para leituras e escritas, garantindo consistência.
2. Replicação Primária/Secundária:
  - Um nó principal coordena as atualizações, enquanto nós secundários mantêm cópias.
3. Algoritmo Gossip:
  - Dissemina informações entre nós de forma probabilística, sendo altamente escalável.

Exemplo: Sistemas de banco de dados distribuídos, como o MongoDB e o Cassandra, utilizam algoritmos de replicação para garantir alta disponibilidade e consistência eventual.