Autor(es):
Veronese, Giuliana Teixeira dos Santos, 1976- 
Data: 2010
Identificador Persistente: http://hdl.handle.net/10451/2304
Origem: Repositório da Universidade de Lisboa
Assunto(s): Engenharia informática; Sistemas distribuídos; Teses de doutoramento - 2010
Descrição
Tese de doutoramento, Informática (Engenharia Informática), Universidade de Lisboa, Faculdade de Ciências, 2010 The growing reliance on wide-area services demands highly available systems that provide
a correct and uninterrupted service. Therefore, Byzantine Fault-Tolerant (BFT) algorithms have
received considerable attention in the last years. A service is replicated over several servers and
can survive even in the presence of a bounded number of Byzantine failures.
The main motivation for this thesis is that for a replicated service to be fault-tolerant,
common mode failures have to be avoided. More specifically, the thesis is concerned with
common mode failures caused by natural disasters, power outages and physical attacks, which
have to be prevented by scattering replicas geographically. This requires the sites where the
replicas reside to be connected by a wide-area network (WAN) like the Internet.
Unfortunately, when the replicas are distributed geographically the performance of current
BFT algorithms is affected by the lower bandwidths, and the higher and more heterogeneous
network latencies. In order to deal with these limitations this thesis introduces novel BFT
algorithms that are simultaneously efficient and secure. Some algorithms of this thesis are based
on a hybrid fault model, i.e., considering that a part of the system is secure by construction. A
notable contribution of this thesis is the definition and implementation of a minimal trusted
service: the Unique Sequential Identifier Generator (USIG).
The thesis describes how to implement a 2 f +1 Byzantine consensus algorithm using a
2 f +1 reliable multicast algorithm that requires a trusted service, that is an abstract version
of the USIG. Then, the USIG service and the reliable multicast primitive are applied as a core
component to implement two novel BFT algorithms introduced in this thesis: MinBFT and
MinZyzzyva. These BFT algorithms are minimal in terms of number of replicas, complexity of
the trusted service used, and number of communication steps. In order to mitigate performance
degradation attacks, this thesis proposes the use of a rotating primary defining a novel BFT
algorithm, Spinning, that is less vulnerable to attacks caused by a faulty primary and attains a
throughput similar to the baseline algorithm in the area. Finally, the mechanisms and techniques developed in this thesis are combined in order to
define EBAWA, a novel BFT algorithm that is suitable for supporting the execution of wide-area
replicated services. O crescimento da dependência na utilização de serviços informáticos em redes de larga escala
demanda sistemas que forneçam um serviço correcto e ininterrupto. Por este motivo,
algoritmos tolerantes a faltas bizantinas (BFT) têm recebido considerável atenção nos últimos
anos. A ideia fundamental destes algoritmos é replicar um determinado serviço num conjunto
de servidores, assegurando a sua operação contínua mesmo na presença de um número limitado
de servidores faltosos. Cada servidor é uma réplica, uma máquina de estados determinística que
executa operações em resposta a requisições realizadas por clientes.
Para que serviços replicados sejam tolerantes a faltas, modos comuns de falhas devem
ser evitados, essa ´e a principal motivação desta tese. Mais especificamente, a tese trata de
falhas causadas por desastres naturais, falta de energia e ataques físicos. Para que a ocorrência
destas falhas afecte um número limitado de servidores é necessário distribuir as réplicas
geograficamente. Esta distribuição, requer que os locais onde se situam as réplicas sejam
conectados por uma rede de larga-escala (WAN), como a Internet.
Infelizmente, quando as réplicas estão distribuídas geograficamente o desempenho dos
algoritmos BFT actuais é afectado pelas limitações de largura de banda e latências heterogéneas,
típicas em redes de larga-escala. A fim de tratar destas limitações esta tese introduz novos
algoritmos BFT que são simultaneamente eficientes e seguros. Alguns destes algoritmos são
baseados em um modelo de faltas híbrido, por exemplo, parte do sistema ´e considerado seguro
pela sua construção. Uma importante contribuição desta tese é a definição e concretização de
um serviço confiável mínimo: o gerador de identificador único e sequencial (USIG).
A tese descreve como concretizar algoritmos de consenso bizantinos com 2 f +1 processos,
usando um algoritmo de reliable multicast que requer um componente confiável, uma abstração
do USIG. O serviço USIG e a primitiva de reliable multicast são aplicados como componentes
nucleares na concretização de dois novos algoritmos BFT introduzidos nesta tese: MinBFT e
MinZyzzyva. Estes algoritmos são mínimos em termos de número de réplicas, complexidade do
componente confiável e número de passos de comunicação.
A fim de mitigar os ataques de degradação de desempenho esta tese propõe o uso de um primário rotativo, definindo assim um novo algoritmo BFT, o Spinning. Al´em de ser menos
vulnerável a ataques causados por primários faltosos, o Spinning atinge um débito similar ao
algoritmo base. Finalmente, os mecanismos e técnicas desenvolvidos ao longo desta tese são
combinados com o objectivo de definir o EBAWA, um novo algoritmo BFT que é adequado para
suportar a execução de serviços replicados em redes de larga-escala.
