# Tolerância a falhas

Eleição de líder, two-phase commit e primary-backup, com uma eleição em anel resolvida passo a passo.

Página: https://resumos.rgo.pt/cadeiras/cpd/tolerancia-falhas/

Num sistema distribuído, máquinas falham enquanto as outras continuam. A tolerância a falhas é o conjunto de protocolos que mantém o serviço correto apesar disso. Esta página cobre os três que a ficha exige, com garantias de cada um.

## Eleição de líder

Muitos sistemas precisam de exatamente um coordenador. Quando o líder falha, os sobreviventes elegem outro. No algoritmo de **anel** (Chang-Roberts), os processos formam um anel lógico e cada um conhece só o seu sucessor. Quem deteta a falha envia uma mensagem de eleição com o seu identificador. Cada processo reencaminha o maior identificador que já viu e descarta os menores. Quando um processo recebe o seu próprio identificador de volta, sabe que é o maior do anel e anuncia-se coordenador.

## Exemplo completo

Quatro processos com identificadores 2, 5, 7 e 9 em anel, pela ordem 2, 5, 7, 9. O líder 9 falha e o processo 5 deteta primeiro.

1.  O 5 envia `eleição(5)` ao seu sucessor, o 7.
2.  O 7 compara, 5 é menor que 7, por isso substitui e envia `eleição(7)` ao 2.
3.  O 2 compara, 7 é maior que 2, reencaminha `eleição(7)` ao 5.
4.  O 5 compara, 7 é maior que 5, reencaminha `eleição(7)` ao 7.
5.  O 7 recebe o seu próprio identificador. É o maior, declara-se líder e envia `coordenador(7)` a dar a volta ao anel.

Total de mensagens de eleição: 4, uma por processo, mais 3 de anúncio. Se o 2 tivesse detetado a falha primeiro, teria enviado `eleição(2)`, que o 5 substituiria por 5 e o 7 por 7, com o mesmo vencedor. O invariante é esse, o maior identificador sobrevivente dá sempre a volta completa e vence.

![Anel com os processos 2, 5 e 7 mais o 9 assinalado como falhado. A mensagem eleição com 7 circula pelos três sobreviventes.](https://resumos.rgo.pt/cadeiras/cpd/tolerancia-falhas/figura-1.svg)

## Two-phase commit e primary-backup

O **two-phase commit** (2PC) garante que uma transação distribuída ou acontece em todos os participantes ou em nenhum. O coordenador pergunta a todos se podem confirmar (fase 1) e só envia a ordem de confirmação se todos disserem sim (fase 2). A garantia, atomicidade total, paga-se com bloqueio, se o coordenador falha a meio, os participantes ficam presos à espera.

![Sequência do two-phase commit. O coordenador pergunta preparar, os participantes votam sim, e o coordenador ordena confirmar. Se falhar entre o voto e a ordem, os participantes bloqueiam.](https://resumos.rgo.pt/cadeiras/cpd/tolerancia-falhas/figura-2.svg)

[Vídeo: Two Phase Commit to power Distributed Transactions in a Distributed System](https://www.youtube.com/watch?v=sZVCpjuVUL8)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=sZVCpjuVUL8)

O **primary-backup** (primário apoio) replica um serviço com um primário que executa e um apoio que observa. O primário envia atualizações de estado ao apoio. Se o primário falha, o apoio assume depois de uma eleição. A garantia é continuidade do serviço, não atomicidade fina como o 2PC, e o custo é o atraso de replicar cada atualização antes de responder ao cliente.

Responde a “quem manda agora”. Usa-se quando o coordenador falha e é preciso exatamente um substituto. Aparece antes do primary-backup e depois de qualquer falha de líder.

Responde a “todos ou nenhum”. Usa-se em transações que tocam várias máquinas, como uma transferência entre duas bases de dados. O preço é o bloqueio se o coordenador falhar a meio.

Responde a “o serviço continua”. Usa-se para um servidor que cai e outro que assume sem interromper os clientes. O preço é replicar cada atualização antes de responder.

## Para saber mais

*   [Transações distribuídas no MIT](https://dsg.csail.mit.edu/6.5830/2022/lectures/lec17-2022.pdf): slides com diagramas de mensagens do two-phase commit.