Evaluación de un esquema adaptable tolerante a falla de tipo bizantinas y crash basado en algoritmos de consenso distribuido

Abstract

Este trabajo realiza una revisión de los principales algoritmos de consenso distribuido para un modelo de fallas de crash o bizantinas, para luego revisar cómo estos pueden resolver un problema presentado por Cloudflare. El trabajo de análisis realizado permite proponer una solución que combine ambos tipos de algoritmos, mediante un mecanismo adaptable que cambie automáticamente de uno a otro, según las condiciones operativas que mida un detector de fallas. Finalmente, se realiza una prueba de concepto con distinto número de peticiones y considerando escenarios sin fallas, con fallas crash y fallas bizantinas, para poder validar que la solución propuesta es mejor que tener implementado solo un algoritmo de fallas bizantinas y su tiempo de ejecución sea considerablemente menor a éste. Estos resultados son relevantes como motivación y base para continuar la investigación en el uso de algoritmos híbridos y adaptables que sean capaces de cambiar de protocolo de resolución de fallas al detectar un comportamiento bizantino.

This work makes a revision of the primary algorithms of distributed consensus for a model of crash or byzantine failures, with that review how those can solve a problem faced by Cloudflare. The analysis work done allows to propose a solution that combines both kind of algorithms, using an adaptable mechanism who changes automatically from one to the other, based on the operative conditions that the failure detector track. Finally, a concept test is done with different number of requests and in cases without failures, with crash failures and byzantine failures, to validate that the proposed solution is better than implement only a byzantine failure algorithm and the execution time is noticeable lower than the latter. This results are relevant as motivation and base to continue the investigation of the use of hybrid and adaptable algorithms that area capable of changing failure resolution protocols upon detection of a byzantine behavior.