Tesis:
Agreement in adversarial environments with anonymous and Byzantine elements
- Autor: MARTÍN RUEDA, Javier
- Título: Agreement in adversarial environments with anonymous and Byzantine elements
- Fecha: 2023
- Materia:
- Escuela: E.T.S.I. DE SISTEMAS INFORMÁTICOS
- Departamentos: SISTEMAS INFORMATICOS
- Acceso electrónico: https://oa.upm.es/76516/
- Director/a 1º: JIMÉNEZ MERINO, Ernesto
- Resumen: El acuerdo es un requisito fundamental en muchos sistemas distribuidos porque es un bloque constructivo básico de la tolerancia a fallos, la replicación, la coordinación, el reparto de carga y la difusión de mensajes, entre otras aplicaciones importantes. En muchos casos reales existen elementos que complican la consecución del acuerdo. Está demostrado que no se puede resolver el problema del Consenso de una forma determinista en los sistemas asíncronos si los procesos pueden fallar con caídas abruptas (crash), lo cual es un escenario base de lo más realista. Se ha llevado a cabo mucha investigación sobre algoritmos que resuelven el problema del Consenso bajo diversas suposiciones y modelos de sistema, y esta tesis contribuye con varios algoritmos nuevos en sistemas donde la existencia de ciertos adversarios lo hacen particularmente difícil.
Hemos estudiado el Consenso en sistemas asíncronos anónimos en los que un adversario puede controlar los dispositivos que suelen usarse para resolver el problema. Los sistemas anónimos añaden la difcultad de que no se puede distinguir a los procesos entre sí. Bajo el modelo de fallos de caída abrupta y parada (crash-stop) y la existencia de canales de comunicación fables, hemos especifcado y demostrado formalmente un algoritmo que utiliza un enfoque híbrido en el que combinamos un detector de fallos de la clase A y un dispositivo distribuido de moneda para resolver el Consenso aleatorio incluso si un adversario poderoso es capaz de controlar alguno de estos dispositivos. También se incluye una implementación de un algoritmo de moneda para sistemas asíncronos anónimos que es la primera que se puede hallar en la literatura científca. Las simulaciones que hemos realizado muestran que las prestaciones de nuestros algoritmos parecen ser bastante buenas.
Hemos estudiado el Consenso en sistemas asíncronos en los que algunos de los procesos pueden exhibir fallos bizantinos degenerativos, es decir, cuando un proceso comienza a fallar, se degrada y acaba por fallar permanentemente. En la literatura científca hay otros algoritmos que permiten alcanzar consenso usando detectores de fallos a pesar de la existencia de un número limitado de procesos bizantinos, pero nuestra propuesta destaca porque no requiere que los procesos tengan un conocimiento a priori de la membresía del sistema, y también porque usa un detector de fallos de la clase que está desacoplado del algoritmo de Consenso, a diferencia de las propuestas publicadas anteriormente. Esto simplifca el análisis, la demostración formal y la implementación de los algoritmos. También se incluye la implementación de una primitiva llamada RFLOB que garantiza que los procesos correctos entregan la misma secuencia de mensajes si fueron difundidos por el mismo proceso, y que los mensajes difundidos por cada proceso se entregan en todos los procesos correctos en el mismo orden FIFO y orden local, en sistemas sin membresía conocida donde menos de un tercio de los procesos pueden ser bizantinos.
Hemos estudiado el uso de la cadena de bloques (blockchain) como herramienta para coordinar sistemas de múltiples robots en presencia de agentes bizantinos maliciosos, es decir, robots cuyas acciones y /o comunicaciones intentan frustrar las misiones en grupo. Hemos desarrollado y demostrado formalmente varios algoritmos que se pueden usar en misiones del tipo "seguir al líder" (Follow The Leader) donde menos de un tercio de los robots pueden ser bizantinos, y hemos determinado cotas para algunos parámetros, como el número de movimientos o el tamaño de la cadena de bloques, que proporcionan información sobre la viabilidad de usar estos algoritmos en robots con recursos limitados.
ABSTRACT
Agreement is a fundamental requirement in many distributed systems, because it is a basic building block of fault tolerance, replication, coordination, load balancing, and multicasting, among other important applications. However, many real scenarios include elements which complicate reaching agreement. It is proven that the Consensus problem cannot be solved deterministically in asynchronous systems if processes can fail by crashing, which is a very realistic base scenario. Much research has been done on algorithms that solve Consensus under different asumptions and system models, and this thesis contributes several new algorithms in systems where certain adversaries make it especially diffcult.
We have studied Consensus in anonymous asynchronous systems where an adversary may control the devices typically used to solve the problem. Anonymous systems add the diffculty that processes cannot be distinguished from each other. Under the crash-stop failure model and the assumption of reliable communication channels, we have specifed and formally proven an algorithm which uses a hybrid approach by combining a failure detector of class A and a coin distributed device, in order to solve random Consensus even if a powerful adversary is able to control either of those devices. We also include an implementation of a coin in an anonymous asynchronous system which is a frst in the literature. We have carried out simulations which show that the performance of our algorithms seems to be quite good.
We have studied Consensus in asynchronous systems where some of the processes may exhibit degenerative Byzantine failures, that is, when a process starts failing, it degrades and eventually fails permanently. Other algorithms exist in the scientifc literature that allow to achieve Consensus using failure detectors despite the existence of a limited number of Byzantine processes, but our proposal stands out because it does not require that processes have a priori knowledge of system membership, and also because it uses a failure detector of class which is decoupled from the Consensus algorithm, unlike previously published proposals. This simplifes both analysis, formal proof and implementation of the algorithms. We also include an implementation of a RFLOB primitive which guarantees that correct processes deliver the same sequence of messages if they were broadcast by the same process, and the messages broadcast by each process are delivered by all correct processes following the same FIFO and local order in systems with unknown membership where less that one third of the processes can be Byzantine.
We have studied the use of the blockchain as a tool to coordinate multi-robot systems in the presence of malicious Byzantine agents, that is, robots whose actions and/or communications attempt to thwart group missions. We have developed and formally proven a series of algorithms that can be used in Follow The Leader type missions where less than one third of robots can be Byzantine, and have determined bounds for some parameters, such as number of moves or the blockchain size, which provide insight into the feasibility of using these algorithms in resource-constrained robots.