Author(s): Matos, David Rogério Póvoa de Matos
Date: 2013
Persistent ID: http://hdl.handle.net/10451/10076
Origin: Repositório da Universidade de Lisboa
Subject(s): Sistemas distribuídos; Confiabilidade; Segurança; Tolerância a faltas; Tolerância a intrusões; Acordo; Consenso; Redes ad hoc sem fios; Teses de mestrado - 2013
Tese de mestrado em Engenharia Informática (Arquitectura, Sistemas e Redes de Computadores), apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2013
Consensus plays a fundamental role in distributed systems. This operation consists in having every process in a distributed system, or a subset of processes, to agree upon a value that was proposed by any of the processes. Consensus is used to solve several problems in distributed systems computation, such as: state machine replication, leader election and atomic broadcast, allowing the coordination of the network. Its applicability becomes more important and difficult to implement in wireless ad hoc networks that are vulnerable to intrusions. When dealing with a wireless ad hoc network, specially one composed by mobile devices that are constantly moving, there are several obstacles that have to be overcome such as the unreliability in the communication, the hardware limitations of the devices, the limited communication range and the exposure to malicious users. The project consists in the design, implementation, test and analysis of Byzantine fault-tolerant consensus protocols for wireless ad hoc networks. It is assumed that the number of participants is unknown and the consensus protocols execute in a group of processes called sink. The protocols are byzantine fault-tolerant and circumvent both FLP and Santoro-Widmayer impossibility results. Three forms of consensus protocols were considered: binary, multivalued and vector. The protocols were organized in a stack, where lower level protocols were used to build higher ones. The stack was implemented as a library and was tested in a simulation environment. Some preliminary tests were also performed with Android devices. The evaluation of the protocols shows that they exhibit good performance in several scenarios and even under attack.
O consenso tem um papel fundamental em sistemas distribuídos. Esta operação consiste em ter todos os processos num sistema distribuído, ou um subconjunto de processos, a acordar num valor que foi proposto por algum dos processos. O consenso é usado para resolver vários problemas na computação de um sistema distribuído, como por exemplo: máquina de estados replicada, eleição de líder e difusão atómica, permitindo a coordenação da rede. A sua utilidade torna-se mais importante e difícil de implementar em redes ad hoc móveis sem fios que estão vulneráveis a intrusões. Quando se está a lidar com uma rede ad hoc sem fios, especialmente uma composta por dispositivos móveis que apresentam uma mobilidade constante, existe um conjunto de obstáculos relacionados com a falta de fiabilidade na comunicação, as limitações dos equipamentos, o seu reduzido alcance de comunicação e a exposição¸ ao a utilizadores mal intencionados. O projecto consiste no desenho, implementação, teste e análise de protocolos de consenso tolerantes a faltas bizantinas para redes ad hoc sem fios. ´E assumido que o número de participantes é desconhecido e os protocolos de consenso são executados num grupo de processos denominado poço. Os protocolos são tolerantes a faltas bizantinas e contornam os resultados de impossibilidade de FLP e de Santoro-Widmayer. Foram considerados três tipos de protocolos de consenso: binário, multi-valor e vector. Os protocolos estão organizados numa pilha, onde protocolos de baixo nível foram usados para construir os protocolos de níveis superiores. A pilha foi implementada como uma biblioteca e foi testada em ambiente de simulação. Alguns testes preliminares foram também efectuados com dispositivos Android. A avaliação dos protocolos revela que estes exibem um bom desempenho em vários cenários e mesmo sobre ataque.
