Algoritmo de Difusão Atômica Rápido a Despeito de Colisões Tolerante a Falhas Bizantinas

• Rodrigo Q. Saramago
• Eduardo A. P. Alchieri
• Tuanir F. Rezende
• Lasaro Camargos

Resumo

O uso de protocolos de Difusão Atõmica baseados em Consenso na implementação de Máquinas de Estados Replicadas esbarra na ineficiência destes protocolos na presença de colisões, isto é, propostas simultâneas. Isso porquê propostas não decididas no Consenso (comandos não entregues) devem ser repropostas em novas instâncias, aumentando seu tempo de entrega e atrasando sua execução. O algoritmo CFABCast (Collision-Fast Atomic Broadcast) utiliza uma variante do Consenso, o M-Consenso, para decidir e entregar múltiplos valores por instância. CFABCast, contudo, não tolera falhas bizantinas, requisito importante em diversos cenários. Como primeira contribuição deste artigo, propomos uma versão modificada do CFABCast que tolera falhas bizantinas. Apesar de ser baseado em um algoritmo rápidoá despeito de falhas, nosso algoritmo não é rápido ante a possibilidade de falhas bizantinas. De fato, nossa segunda contribuição é a conjectura de que nenhum algoritmo possa sêlo no modelo assíncrono. Finalmente, nossa terceira contribuição é a proposta de um algoritmo que é rápidoá despeito de falhas bizantinas, contornando a impossibilidade pela extensão do modelo computacional com o componente seguro USIG (Unique Sequential Identifier Generator).