Acordos Bizantinos Aleatorizados

Algoritmos aleatorizados para alcançar Acordo Bizantino foram recentemente propostos em Rabi83. Com esses algoritmos, o acordo é alcançado em um número esperado de fases que é uma constante pequena independente do número de processos n e do número de processos defeituosos t. Os algoritmos em Rabi83 toleram até (n-1)/10 processos defeituosos em sistemas assíncronos, e até (n-1)/4 processos defeituosos em sistemas síncronos. Neste artigo, usando o mesmo modelo de computação que em Rabi83, descrevemos algoritmos que superam até (n-1)/3 processos defeituosos em sistemas assíncronos e até (n-1)/2 processos defeituosos em sistemas síncronos. Com ambos os algoritmos propostos, o acordo é alcançado em um número esperado de fases que é uma constante pequena independente de n e t, mas a complexidade de comunicação é maior do que em Rabi83. Também é mostrado que nenhum algoritmo de Acordo Bizantino pode superar mais do que (n-1)/3 processos defeituosos em sistemas autenticados assíncronos, e portanto o algoritmo assíncrono proposto aqui é ótimo nesse aspecto.