Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL DA BAHIAINSTITUTO DE MATEMÁTICA
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
Murilo Santos de Lima
Protocolo Assíncrono para Detecção de Falhas
Bizantinas em Sistemas Distribuídos Dinâmicos
Salvador
2008
Murilo Santos de Lima
Protocolo Assíncrono para Detecção deFalhas Bizantinas em Sistemas
Distribuídos Dinâmicos
Monografia apresentada ao Curso degraduação em Ciência da Computação,Departamento de Ciência da Computação,Instituto de Matemática, Universidade Fe-deral da Bahia, como requisito parcial paraobtenção do grau de Bacharel em Ciência daComputação.
Orientadora: Profa . Fabíola Gonçalves PereiraGreve
Salvador
2008
“Eu te louvarei, porque de um modo terrível, e tão maravilhoso fui formado;
maravilhosas são as tuas obras, e a minha alma o sabe muito bem.” Salmo 139:14
AGRADECIMENTOS
Ao Deus eterno e triuno, por sua presença e operação constante em minha vida. Em especial
por ter preparado momento tão oportuno para me apresentar Seu projeto de vida. O mérito deste
trabalho (e de toda a minha existência) é dEle, não meu. A Ele atribuo todas as vitórias que
tenho conquistado em todos os aspectos, em especial as mais recentes, principalmente a alegria
que goza meu coração e que todas as riquezas, glórias e conhecimento deste mundo passageiro
não podem proporcionar. A Ele seja toda a glória, honra e poder para todo o sempre.
À minha mãe Maria, por todo seu amor e dedicação, pelos valores que me instruiu e pela
conscientização desde cedo sobre a responsabilidade das minhas decisões e atitudes. Esta vitó-
ria com certeza também é dela. À minha irmã Malu e a seu esposo Thiago pelo apoio, e às suas
filhas Júlia e Lara pela alegria que me têm proporcionado. Aos meus avós Euzébio e Hilda, pelo
carinho. A meu pai Wilson, com quem pude retomar o convívio neste período, pelos poucos
mas valiosos conselhos. À prima Daniela, que foi canal de tal encontro com uma família que
me recebeu tão carinhosamente.
Aos irmãos da Igreja Cristã Maranata e do corpo de Cristo como um todo, mas em especial
da ICM da Pituba, pelo suporte. Sua companhia foi indispensável neste período. Menciono em
especial os nomes de Taíse Campos, Ilton Serafim e pastor Koji, pelos conselhos nos momentos
difíceis. Àqueles que oraram por mim, por esta vitória, mas principalmente para que meus pés
não resvalassem.
Aos professores do DCC/UFBA e do DMAT/UFBA que fazem a diferença (eles sabem
quem são), pelo incentivo. Em especial a Fabíola Greve e Perfilino Jr., meus orientadores de
projeto final e iniciação científica, respectivamente, pelo encorajamento, confiança, atenção e
pelas longas conversas. Vocês foram mais que orientadores! Aos professores de outras épocas
que de alguma forma me inspiraram e ajudaram na formação do meu caráter (prefiro não listar
nomes pra não esquecer de ninguém especial).
Aos sete colegas que me acompanharam mais de perto, denominados “iluminados”: Isa-
que, Ruth, Hugo, José Souza, José Augusto, Waltemir e Antonio Marcos. A Lorena, Jerônimo,
Daniel Couto, André Pacheco, André Fonseca, Caio Tiago e Alexandre “top” pela companhia e
pelas conversas jogadas fora. A veteranos como Amadeu, Charles e Orivaldo, que me mostra-
ram o lado humano dessa profissão de maluco.
Àqueles que conviveram comigo em um dos sete locais diferentes onde morei neste período;
em especial a Andréia Mendes, Iuri Castro, Rafael Chepote e Sílvia Letícia, pela amizade.
Ao pessoal da [2]toks Tecnologia, pelo aprendizado e do Instituto Recôncavo de Tecnolo-
gia, pelo apoio e compreensão neste momento final tão atribulado.
Àqueles cujos nomes não foram citados, mas que fazem parte da minha vida, ficam a grati-
dão e as desculpas por minhas limitações de memória.
Um grande abraço a todos!
RESUMO
Protocolos tolerantes a faltas são fundamentais no projeto de sistemas distribuídos confiá-veis. Em um sistema distribuído dinâmico, no qual os nós podem entrar e sair da rede aleatori-amente, a qualquer momento da execução do sistema, o desafio de prover tais serviços é aindamaior. Adicionalmente, devido à larga escala de participantes e ao uso comum de comunicaçãosem fio, não é possível prover aos processos uma visão global da topologia da rede, de formaque cada nó tem um conhecimento parcial da composição do sistema.
Um fator preocupante, em especial, é a segurança, uma vez que a dinamicidade da popula-ção dos nós facilita a ação de agentes maliciosos sobre o sistema. O modelo de falhas bizantinaslida com este tipo de ataque assumindo a existência de processos corruptos, que podem se com-portar de maneira arbitrária na tentativa de impedir que o sistema funcione conforme a suaespecificação. O sistema tolera tais faltas se, apesar do comportamento maligno de alguns deseus processos, ele mantém o seu funcionamento correto.
A abstração de detectores de falhas proposta por Chandra e Toueg provê uma forma modu-lar de tratar as falhas em sistemas assíncronos, separando tal tarefa do protocolo distribuído queos utiliza. Trabalhos recentes foram propostos para implementação da detecção de falhas emsistemas distribuídos dinâmicos, embora nenhum deles lide com a ocorrência de falhas bizan-tinas. Este trabalho apresenta então um detector assíncrono de falhas bizantinas para sistemasdistribuídos dinâmicos. O mesmo baseia-se no detector assíncrono proposto por Sens et al. ena abordagem de detecção de falhas bizantinas descrita por Kihlstrom et al..
Palavras-chave: detectores de falhas, falhas bizantinas, sistemas distribuídos dinâmicos,sistemas auto-organizáveis, detectores de falhas assíncronos.
ABSTRACT
Fault-tolerant protocols are a fundamental part of the reliable distributed systems project.In a dynamic distributed system, in which nodes may join and leave the network randomly, atany moment of the system execution, these services are even harder to provide. Moreover, dueto the large participant scale and the common use of wireless communication, it is not possibleto provide the processes with a global view of the network topology, so that each node only hasa partial knowledge of the system composition.
A specially alarming factor is the security, as the dynamism of the node population furthersthe action of malicious agents over the system. The Byzantine failure model tries to deal withsuch insecurity by supposing the existence of corrupted processes, which may behave in anarbitrary manner, trying to hinder the system to work accordingly to its specification. Thesystem tolerates those faults if, despite the malicious behavior of some of its processes, it keepsa correct functioning.
The failure detector abstraction proposed by Chandra and Toueg provides a modular ap-proach to deal with failures on asynchronous systems, separating such task from the distributedprotocol that uses it. Recent work has proposed the failure detection implementation on dyna-mic distributed systems, though the occurrence of Byzantine failures is not dealt with. In thiswork, we present an asynchronous Byzantine failure detector for dynamic distributed systems.It is based on the asynchronous detector proposed by Sens et al. and on the Byzantine failuredetection approach described by Kihlstrom et al..
Keywords: failure detectors, Byzantine failures, dynamic distributed systems, self-organizingsystems, asynchronous failure detectors.
LISTA DE SÍMBOLOS
♦S classe de detectores de falhas com completude forte e precisão
fraca após um tempo,
p. 34
♦S (Byz,A ) classe de detectores de falhas bizantinas com completude forte bi-
zantina e precisão fraca após um tempo,
p. 37
Ω oráculo distribuído de detecção de líder, p. 35
Π conjunto de processos que compõem um sistema distribuído, p. 17
⊥ valor indefinido, p. 27
δ tempo de transmissão estimado de uma mensagem, p. 22
ε diferença máxima tolerada entre os valores decididos por dois pro-
cessos diferentes no consenso aproximado,
p. 29
A algoritmo para o qual um detector de falhas bizantinas é projetado, p. 37
MP propriedade de inclusão, p. 44
RP propriedade de receptividade, p. 44
1→ n padrão de comunicação em que apenas um processo envia mensa-
gens,
p. 46
byz_rec_ f romtj conjunto de pelo menos d− f processos dos quais p j recebeu a
mensagem requerida por A no passo em execução no instante t,
p. 49
ByzMP propriedade de inclusão bizantina, p. 49
ByzRP propriedade de receptividade bizantina, p. 49
d densidade da área de cobertura em um grafo de comunicação de
uma rede dinâmica,
p. 42
f número máximo de processos faltosos que o sistema distribuído
pode tolerar,
p. 18
G(V,E) grafo com conjunto V de vértices e E de arestas que caracteriza a
topologia de uma rede de comunicação,
p. 41
k grau de conectividade do detector de participação k-OSR, p. 32
Kti conjunto de processos que receberam uma mensagem QUERY de
pi até o instante t,
p. 44
KBti conjunto de processos que receberam uma mensagem SUSPICION
de pi até o instante t,
p. 49
n→ n padrão de comunicação em que todos os processos trocam mensa-
gens entre si a cada passo,
p. 45
p−→ q canal de comunicação entre dois processos p e q, p. 22
p,q, pi, p j processos em um sistema distribuído, p. 17
rangei vizinhança definida pela área de cobertura de um processo pi em
uma rede dinâmica,
p. 41
rec_ f romtj conjunto de pelo menos d− f processos dos quais p j recebeu res-
postas à mensagem QUERY que terminou antes ou no instante t,
p. 44
t,u variáveis de tempo global, desconhecidas pelos processos, p. 40
V conjunto de possíveis valores propostos/decididos no problema do
consenso,
p. 26
v valor proposto/decidido no problema do consenso, p. 26
vi,vp,vq valores propostos por determinados processos no problema do con-
senso,
p. 26
LISTA DE ABREVIATURAS E SIGLAS
k-OSR classe de detectores de participação necessária para a realização do
FT-CUP,
p. 32
BFT-CUP consenso tolerante a faltas bizantinas com participantes desconhe-
cidos,
p. 32
CUP consenso com participantes desconhecidos, p. 31
FD detector de falhas (failure detector), p. 33
FLP impossibilidade de resolver consenso em sistemas completamente
assíncronos na ocorrência de falhas (iniciais dos autores de (FIS-
CHER; LYNCH; PATERSON, 1985)),
p. 29
FT-CUP consenso com participantes desconhecidos tolerante a faltas, p. 31
MANET rede móvel auto-organizável, do inglês mobile ad-hoc network, p. 24
OSR classe de detectores de participação cujo grafo de conhecimento é
redutível a um único poço,
p. 31
P2P rede entre pares, do inglês peer-to-peer, p. 24
LISTA DE TABELAS
2.1 Nomenclatura para sistemas parcialmente síncronos . . . . . . . . . . . . . . . 19
3.1 Número mínimo de processos necessários para resolver consenso em sistemas
estáticos tolerando f processos faltosos (DWORK; LYNCH; STOCKMEYER,
1988) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Condições para realização do consenso em sistemas com participantes desco-
nhecidos (ALCHIERI et al., 2008) (adaptada) . . . . . . . . . . . . . . . . . . 31
4.1 Classes de detectores de falhas obtidas pela combinação das propriedades de
completude e precisão (CHANDRA; TOUEG, 1996) . . . . . . . . . . . . . . 34
4.2 Classes de detectores de falhas bizantinas (KIHLSTROM; MOSER; MELLIAR-
SMITH, 2003) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
LISTA DE FIGURAS
2.1 Hierarquia de gravidade das classes de falhas de processos (adaptado de (HAD-
ZILACOS; TOUEG, 1993)) . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Categorização das falhas bizantinas (KIHLSTROM; MOSER; MELLIAR-SMITH,
2003) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.1 Área de cobertura em uma rede de comunicação sem fio . . . . . . . . . . . . 41
5.2 Grafo de comunicação para a rede da Figura 5.1 . . . . . . . . . . . . . . . . . 42
5.3 Grafo de uma rede com f -cobertura bizantina ( f = 1) . . . . . . . . . . . . . . 43
5.4 Funcionamento do mecanismo de query/response proposto em (SENS et al.,
2008) (d = 5, f = 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 Mecanismo de espera de mensagens do protocolo proposto (d = 5, f = 1) . . . 45
5.6 Geração de suspeitas no protocolo proposto ( f = 1) . . . . . . . . . . . . . . . 46
5.7 Geração de equívocos no protocolo proposto ( f = 1) . . . . . . . . . . . . . . 47
5.8 Detecção de falhas por comissão no protocolo proposto ( f = 1) . . . . . . . . . 47
5.9 Processo corrupto que envia mensagens com valores diferentes para processos
diferentes (supor x 6= y, y 6= z ou x 6= z) . . . . . . . . . . . . . . . . . . . . . . 48
5.10 Inclusão de um processo novo no sistema com base na propriedade ByzMP
( f = 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.11 Comportamento de um processo que atende à propriedade ByzRP (d = 4, f = 1) 50
SUMÁRIO
1 Introdução 14
1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Modelos de Sistemas Distribuídos 17
2.1 Modelos síncrono vs. assíncrono . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Modelos de falhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Falhas de processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Falhas de canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 Falhas bizantinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Sistemas distribuídos dinâmicos . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Problema do Consenso 26
3.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.1 Consenso bizantino . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.2 Consenso uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.3 Outras definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Soluções existentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Limites de tolerância a faltas na resolução do consenso . . . . . . . . . . . . . 30
3.3.1 Resultados para sistemas distribuídos dinâmicos . . . . . . . . . . . . 31
4 Detectores de Falhas Não-Confiáveis 33
4.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.1 Detecção de líder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Detectores de falhas por colapso . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Detectores de falhas bizantinas . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3.1 Detectores de falhas bizantinas segundo Kihlstrom et al. . . . . . . . . 37
4.4 Detectores de falhas com participantes desconhecidos . . . . . . . . . . . . . . 38
5 Detector Assíncrono de Falhas Bizantinas com Participantes Desconhecidos 40
5.1 Modelo de sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Funcionamento do detector de falhas por colapso de Sens et al. . . . . . . . . . 43
5.3 Funcionamento do protocolo proposto . . . . . . . . . . . . . . . . . . . . . . 44
5.4 Propriedades comportamentais . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.5 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.6 Esboço de prova de corretude . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6 Conclusão 59
6.1 Dificuldades encontradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Referências Bibliográficas 61
14
1 INTRODUÇÃO
É cada vez maior nos dias atuais a demanda por aplicações com requisitos de alta dispo-
nibilidade e confiabilidade. Em aplicações críticas, como no controle de transações bancárias,
uma operação incorreta pode levar a prejuízos financeiros enormes. Uma vez que é impossí-
vel construir sistemas computacionais que nunca falhem (VERISSIMO; RODRIGUES, 2001),
tais requisitos só podem ser atendidos pelo uso de redundância e de distribuição, seja física ou
lógica, dos recursos computacionais (SCHNEIDER, 1993a). Se um componente falhar, uma
réplica assume seu lugar, de forma que o sistema como um todo continua sua operação normal.
Uma etapa fundamental desse processo é o desenvolvimento de protocolos tolerantes a faltas
(GREVE, 2005), necessários para coordenar as ações dos diversos componentes do sistema.
O barateamento do hardware e de conexões de banda larga tem levado ao surgimento de
um número cada vez maior de aplicações distribuídas que utilizam a Internet como meio de
comunicação. Em paralelo, com a diminuição do custo de comunicação sem fio, a demanda
por aplicações para dispositivos móveis tem crescido. Nesses contextos, fatores como alta la-
tência de transmissão, memória limitada e baixo poder de processamento dificultam a criação
de sistemas escaláveis e eficientes. O modelo de sistemas distribuídos dinâmicos (AGUILERA,
2004; MOSTEFAOUI et al., 2005), representado pelas redes peer-to-peer, redes móveis auto-
organizáveis, redes de sensores sem fio e grades computacionais abertas, buscam lidar com
essas questões. O mesmo é caracterizado por uma população de nós que podem entrar e sair
da rede aleatoriamente, a qualquer momento da execução do sistema. Adicionalmente, não é
possível prover aos processos uma visão global da topologia da rede, de forma que cada nó tem
um conhecimento parcial da composição do sistema. Constata-se, portanto, que os protocolos
distribuídos clássicos, que supõem uma rede com composição estática e conhecida, não são
mais adequados neste novo contexto.
Um fator preocupante em sistemas dinâmicos, em especial, é a segurança. A dinamicidade
da população dos nós e o uso comum de redes sem fio ou da Internet como meios de comuni-
cação facilitam a ação de agentes maliciosos sobre o sistema. O modelo de falhas bizantinas
(LAMPORT; SHOSTAK; PEASE, 1982) lida com este tipo de ataque assumindo a existência de
processos corruptos, que podem se comportar de maneira arbitrária na tentativa de impedir que
15
o sistema funcione conforme a sua especificação. Um processo bizantino pode, por exemplo,
tentar assumir a identidade de outro, enviar mensagens com valores incorretos, duplicar men-
sagens ou simplesmente não enviar mensagens que o protocolo especificar. O desenvolvimento
de sistemas tolerantes a faltas bizantinas, isto é, que mantenham o seu funcionamento correto
apesar do comportamento maligno de alguns de seus processos, é portanto de especial interesse.
A abstração de detectores de falhas proposta por Chandra e Toueg (CHANDRA; TOUEG,
1996) provê uma forma modular de tratar as falhas em sistemas assíncronos (SCHNEIDER,
1993a), isto é, sistemas que não atendam a restrições temporais. O detector separa o tratamento
das falhas e os requisitos de sincronia do protocolo distribuído que o utiliza, de forma que este
pode lidar apenas com a tarefa a que se propõe. Trabalhos recentes foram propostos para im-
plementação da detecção de falhas em sistemas distribuídos dinâmicos (GUPTA; CHANDRA;
GOLDSZMIDT, 2001; FRIEDMAN; TCHARNY, 2005; SENS et al., 2008), embora nenhum
deles lide com a ocorrência de falhas bizantinas.
Este trabalho apresenta então um detector assíncrono de falhas bizantinas para sistemas dis-
tribuídos dinâmicos. O protocolo proposto baseia-se no detector assíncrono para sistemas com
participantes desconhecidos de Sens et al. (SENS et al., 2008). O tratamento das falhas bizan-
tinas segue a abordagem descrita por (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003).
1.1 OBJETIVO
O objetivo deste trabalho é propor um protocolo assíncrono de detecção de falhas bizan-
tinas para sistemas distribuídos dinâmicos. Para tanto, são revisados os modelos de sistemas
distribuídos propostos na literatura, em especial o modelo de falhas bizantinas e de sistemas
distribuídos dinâmicos; o problema do consenso, como problema fundamental no projeto de
sistemas distribuídos confiáveis e a abstração de detectores de falhas.
1.2 TRABALHOS RELACIONADOS
Os detectores de falhas não-confiáveis foram propostos originalmente por Chandra e Toueg
(CHANDRA; TOUEG, 1996). Desde então diversas implementações têm sido propostas, a
maioria delas baseando-se no uso de mensagens do tipo “eu estou vivo” (I’m alive) e em
uma composição de processos estática e conhecida (LARREA; FERNÁNDEZ; ARÉVALO,
2000). (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003) e (BALDONI; HÉLARY; PIER-
GIOVANNI, 2007) propõem implementações para o modelo de falhas bizantino.
16
Detectores de falhas que lidem com questões inerentes a sistemas dinâmicos incluem (GUPTA;
CHANDRA; GOLDSZMIDT, 2001; FRIEDMAN; TCHARNY, 2005), o primeiro tratando de
populações de nós dinâmicas, o segundo de mobilidade nos nós. Ambos utilizam o mecanismo
de temporização para detecção das falhas. (MOSTEFAOUI; MOURGAYA; RAYNAL, 2003)
apresenta detectores de falhas assíncronos, no entanto para redes com composição conhecida e
estática. Em (SENS et al., 2008) propõe-se, então, a implementação assíncrona de um detector
de falhas que trata tanto a dinamicidade da composição da rede quanto a mobilidade dos nós,
sendo utilizado como base para o desenvolvimento deste trabalho.
1.3 ORGANIZAÇÃO DO TEXTO
Este trabalho encontra-se estruturado da seguinte forma: no Capítulo 2, apresenta-se uma
revisão dos modelos de sistemas distribuídos propostos na literatura, modelos de falhas e de
canais de comunicação, destacando-se ao final o modelo de sistemas distribuídos dinâmicos. O
Capítulo 3 apresenta como ilustração o problema do consenso e seus paradigmas de resolução,
por ser um problema básico no projeto de sistemas confiáveis que pode fazer uso de detecto-
res de falhas para obter soluções em sistemas assíncronos. No Capítulo 4 apresentam-se os
detectores de falhas não-confiáveis e suas extensões para modelos de falhas bizantinas e sis-
temas dinâmicos. O Capítulo 5 apresenta o protocolo desenvolvido. Por fim, no Capítulo 6
apresentam-se as conclusões, dificuldades encontradas e propostas de trabalhos futuros.
17
2 MODELOS DE SISTEMASDISTRIBUÍDOS
Um sistema distribuído é composto por um conjunto Π de n processos (Π = p1, p2, . . . , pn)que se comunicam apenas trocando mensagens através de uma rede de comunicação, de forma
que cada processo não tem conhecimento completo sobre o estado interno dos demais. Especi-
ficamente, é impossível prover uma noção de tempo global perfeitamente sincronizado (LAM-
PORT, 1978). Se não for possível estimar com precisão os limites de tempo de transmissão dos
canais de comunicação e as taxas de diferença na velocidade dos processadores, são necessários
mecanismos adicionais para sincronizar as ações entre os processos do sistema. Em sistemas
altamente instáveis, como a Internet, supor a existência de estimativas precisas deste de tipo não
é realista.
Apesar da complexidade inerente ao seu projeto e construção, sistemas distribuídos são a
solução mais eficaz na construção de sistemas confiáveis e robustos (VERISSIMO; RODRI-
GUES, 2001). Como é impossível construir sistemas computacionais que nunca apresentem
falhas, como defeitos de hardware, falhas na programação de software ou danos causados por
falta de eletricidade ou desastres naturais, é desejável que o sistema como um todo continue a
funcionar mesmo na presença de tais eventos. Uma vez que um ou mais componentes fuja da
sua especificação, os demais componentes podem ser utilizados para tomar providências que
garantam o funcionamento correto do sistema. Para tanto, é necessário que as falhas nos com-
ponentes sejam independentes (SCHNEIDER, 1993a), o que é obtido pela distribuição, tanto
física quanto lógica, dos recursos e das responsabilidades do sistema.
Define-se, por conseguinte, falha como o desvio do sistema como um todo de sua especifi-
cação. A causa original das falhas é denominada falta, que no entanto pode passar desaperce-
bida até que um erro ocorra. Caso o erro reflita em um comportamento incorreto que possa ser
percebido pelo usuário, o sistema apresentou uma falha. Em sistemas formados por diversos
componentes, a falha de um componente pode ser vista como uma falta no sistema, levando a
uma aplicação recursiva das definições apresentadas. Adota-se neste trabalho a tradução falta
para fault, erro para error e falha para failure. Alguns autores, no entanto, traduzem fault como
falha e failure como defeito (COULOURIS; DOLLIMORE; KINDBERG, 2007).
18
Um sistema será, portanto, tolerante a faltas se, apesar do comportamento incorreto de
alguns de seus componentes, atender à sua especificação. Em especial, define-se o grau de re-
siliência f de um sistema como o número máximo de componentes que podem faltar sem que
o serviço prestado seja prejudicado. Esta definição distingue-se da noção de auto-estabilização
(SCHNEIDER, 1993b), na qual garante-se que, mesmo que o sistema alcance um estado errô-
neo, convergirá para um estado correto após um número finito de passos.
A seguir são apresentados os tipos de suposições realizadas no projeto de algoritmos distri-
buídos. A definição de um modelo adequado para o sistema é fundamental para que se possam
realizar deduções teóricas do comportamento do sistema consistentes com a realidade prática
(SCHNEIDER, 1993a).
2.1 MODELOS SÍNCRONO VS. ASSÍNCRONO
Um sistema distribuído é síncrono quando a velocidade relativa dos processadores e os
atrasos nas entregas das mensagens pelos canais de comunicação atendem a limites estabeleci-
dos (SCHNEIDER, 1993a). Em situações controladas, como em redes locais ou em sistemas de
tempo real crítico, em que é possível ou necessário ter limites de tempo controlados, a suposição
de um sistema síncrono é razoável.
Entretanto, conforme mencionado anteriormente, nem sempre é possível definir limites de
tempo adequados: uma avaliação otimista pode levar a faltas constantes, enquanto que uma
avaliação pessimista pode degradar o desempenho do sistema. Para tanto, propõe-se a definição
de sistemas assíncronos, nos quais não são feitas quaisquer suposições temporais.
Por essa característica, um protocolo construído para um sistema assíncrono funcionará em
sistemas síncronos. Conseqüentemente, o desenvolvimento de protocolos assíncronos é desejá-
vel, assim como o estudo de quais problemas podem ser resolvidos de forma assíncrona. Entre-
tanto, um protocolo síncrono será geralmente mais eficiente e simples que um correspondente
assíncrono.
Existem diversos problemas que não podem ser resolvidos em sistemas assíncronos, como
por exemplo o problema do consenso (ver Capítulo 3). Para contornar tal limitação sem apelar
para o uso de suposições fortes de sincronia, foram propostos modelos de sincronia parcial
(DWORK; LYNCH; STOCKMEYER, 1988). Nesse tipo de sistema, existem limites no tempo
de processamento e nas transmissões das mensagens, mas os mesmos não são conhecidos. O
sistema pode ainda passar por períodos de instabilidade, isto é, períodos em que os limites tem-
porais não são respeitados, desde que em algum momento no futuro apresente comportamento
19
síncrono por um período suficiente para garantir a execução da computação distribuída.
Define-se um modelo de processos parcialmente síncronos quando o relaxamento das res-
trições temporais são aplicadas especificamente às velocidades relativas dos processadores ou
aos atrasos relativos dos relógios. De forma similar, sincronia parcial nos canais refere-se a
alterações nas propriedades dos limites no atraso das entregas das mensagens. Este tipo de
suposição subentende que o restante do sistema se comporta de maneira síncrona, levando à
nomenclatura da Tabela 2.1.
Sincronia Sincroniacondições de canais parcial de canaisSincronia sistema síncrono canais parcialmente
de processos síncronosSincronia processos sistemaparcial de parcialmente parcialmenteprocessos síncronos síncrono
Tabela 2.1: Nomenclatura para sistemas parcialmente síncronos
2.2 MODELOS DE FALHAS
Modelos de falhas descrevem a forma como os processos e canais de comunicação em
um sistema distribuído podem falhar. Diferentes suposições sobre as falhas de um sistema
influenciam na solubilidade de determinados problemas e na complexidade das soluções.
Os componentes principais em um sistema distribuído são os processos que realizam a
computação e os canais que transmitem as mensagens. A modelagem das falhas, portanto,
concentra-se em torno desses dois elementos. A seguir, são apresentadas as categorias de falhas
de processos e de canais abordadas na literatura. Dá-se especial atenção, em seguida, ao modelo
de falhas bizantinas, por ser o foco de estudo deste trabalho.
2.2.1 FALHAS DE PROCESSO
Os tipos de falhas que um processo em um sistema distribuído pode cometer são (HADZI-
LACOS; TOUEG, 1993; SCHNEIDER, 1993a):
• Parada (failstop): quando um processo p falha ele pára; os demais processos têm conhe-
cimento de que p falhou. Na prática este modelo é pouco utilizado, uma vez que só pode
ser implementado em um sistema completamente síncrono (SCHNEIDER, 1993a).
20
• Colapso (crash): quando um processo p falha ele pára; os demais processos não têm
conhecimento de que p falhou.
• Omissão na recepção: um processo pode falhar por colapso ou por não receber mensa-
gens que lhe foram enviadas.
• Omissão no envio: um processo pode falhar por colapso ou por não enviar mensagens
que supostamente deveria. Isto é, a especificação do algoritmo determina que o processo
deveria enviar uma mensagem, mas ele falha por não enviá-la.
• Omissão genérica: um processo pode falhar por omissão no envio ou na recepção.
• Omissão temporal: (aplicável apenas a sistemas síncronos) um processo falha por não
executar sua tarefa dentro do limite de tempo especificado.
• Arbitrária (ou bizantina): um processo pode falhar apresentando comportamento arbi-
trário, inclusive malicioso. Isso inclui a corrupção e a forjadura de mensagens. Conjuntos
de processos com este tipo de comportamento podem se unir no intento de derrubar o sis-
tema. Este modelo será abordado com maiores detalhes na Seção 2.2.3.
• Arbitrária com autenticação de mensagens: um processo pode cometer falhas bizan-
tinas, mas existe um mecanismo de autenticação de mensagens que atribui assinaturas
digitais às mesmas, possibilitando a detecção de quando um processo tenta assumir a
identidade de outro.
Evidencia-se uma hierarquia de “gravidade” das falhas, de forma que uma classe de falhas
A é mais grave que outra B se o conjunto de comportamentos faltosos permitidos em B é um
subconjunto próprio daqueles permitidos por A. Neste caso, um algoritmo que tolere falhas do
tipo A também tolerará falhas do tipo B (HADZILACOS; TOUEG, 1993). Observa-se ainda
transitividade nessa relação de gravidade. Na Figura 2.1, mostra-se tal hierarquia entre as clas-
ses de falhas descritas como um grafo direcionado, no qual uma aresta saindo de A para B indica
que A é menos grave que B. A classe das falhas bizantinas é, portanto, a mais grave, de forma
que um algoritmo tolerante a faltas bizantinas tolera qualquer tipo de falta. A figura eviden-
cia ainda a noção de falhas benignas, que incluem todas as classes nas quais não se apresenta
comportamento arbitrário.
Um processo em uma computação distribuída será correto ou falho. Um processo correto
é aquele que não falha durante toda a computação; caso contrário o processo é falho. Um
processo correto sempre funciona de acordo com sua especificação.
21
Figura 2.1: Hierarquia de gravidade das classes de falhas de processos (adaptado de (HADZI-LACOS; TOUEG, 1993))
2.2.2 FALHAS DE CANAL
Um canal de comunicação pode falhar de uma das seguintes formas (HADZILACOS;
TOUEG, 1993):
• Colapso (crash): o canal pára de funcionar, não transmitindo mais mensagens que lhe
são submetidas.
• Omissão: o canal não entrega parte das mensagens que lhe são submetidas.
• Arbitrária (ou bizantina): o canal apresenta comportamento arbitrário (inclusive mali-
cioso), podendo por exemplo transmitir mensagens que não foram enviadas por nenhum
processo ou duplicar mensagens.
• Temporal: (aplicável apenas a sistemas síncronos) o canal não respeita os limites de
tempo de transmissão das mensagens estabelecidos em sua especificação.
Definem-se na literatura diversos modelos de canais de comunicação, que especificam o
comportamento de entrega das mensagens, especialmente em períodos de instabilidade do sis-
22
tema. Neste trabalho, para efeito de simplicidade dos algoritmos propostos, adota-se o modelo
de canais confiáveis. Outros modelos incluem canais com perda de mensagens e canais expirá-
veis (AGUILERA et al., 2001).
Um canal confiável p −→ q entre dois processos p e q atende às seguintes propriedades
(AGUILERA et al., 2001):
• Não criação e não duplicação: q só recebe uma mensagem m de p se este a enviou
anteriormente e m é recebida no máximo uma vez.
• Não atraso na entrega em períodos de estabilidade: seja δ o tempo de transmissão esti-
mado de uma mensagem. Se p envia m a q no tempo t e p −→ q permanece estável no
período [t, t +δ ], então q recebe m antes de ou até t +δ .
• Não perda: se p envia m a q então q recebe m de p em algum momento futuro, desde que
q não falhe.
2.2.3 FALHAS BIZANTINAS
O modelo de falhas bizantinas supõe que os processos podem falhar de maneira arbitrária,
inclusive maliciosa. Tal suposição na prática é bastante realista, tendo em vista os problemas
de segurança enfrentados em sistemas distribuídos e redes de computadores em geral. Situa-
ções que podem levar os processos a se comportarem de maneira arbitrária incluem a ação de
invasores, a corrupção de um programa por um cavalo de Tróia ou ainda situações não intencio-
nais, como erros na programação do software e interferências físicas no hardware, comuns por
exemplo em aplicações espaciais (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003).
Este modelo foi apresentado inicialmente em (LAMPORT; SHOSTAK; PEASE, 1982),
que exibe uma solução para problemas de acordo em sistemas síncronos em função de uma
primitiva de difusão confiável. As seguintes suposições são feitas sobre a comunicação entre os
processos:
• Cada mensagem correta enviada é entregue corretamente. Isto leva à suposição de canais
confiáveis (ver Seção 2.2.2) ou de uma camada de roteamento seguro.
• O receptor da mensagem conhece o remetente. O próprio meio de comunicação pode
atender a tal requisito; caso contrário, podem ser utilizados mecanismos de autenticação
de mensagens (RIVEST; SHAMIR; ADLEMAN, 1978).
23
• A ausência de uma mensagem pode ser detectada pelos processos corretos. Em sistemas
parcialmente síncronos, tal serviço não é fácil de implementar, sendo na verdade abordado
adiante como um dos tipos de falhas que devem ser tratadas quando se deseja lidar com
falhas bizantinas.
No trabalho de Lamport et al., evidenciam-se duas formas de lidar com a presença de pro-
cessos maliciosos: a redundância da informação e o uso de assinaturas digitais não-forjáveis.
Ambas buscam prover aos processos corretos uma visão coerente das mensagens enviadas por
cada processo Estas técnicas, no entanto, não garantem que as mensagens enviadas pelos pro-
cessos faltosos sejam consistentes com os requisitos do algoritmo sendo executado. Uma forma
de lidar com tal situação é a adição de informação adicional às mensagens, na forma de certi-
ficados, que possam ser utilizados para validar o conteúdo sendo transmitido (KIHLSTROM;
MOSER; MELLIAR-SMITH, 2003).
A seguir apresenta-se uma caracterização dos tipos de falhas bizantinas que podem ocorrer,
descrita em (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003). Outras abordagens neste
sentido incluem (BALDONI et al., 1999).
CATEGORIZAÇÃO DE FALHAS BIZANTINAS SEGUNDO KIHLSTROM ET AL.
A Figura 2.2 ilustra os tipos de falhas bizantinas descritas em (KIHLSTROM; MOSER;
MELLIAR-SMITH, 2003). Distinguem-se duas classes de falhas principais: detectáveis, quando
comportamento externo do processo faltoso fornece evidências de que o mesmo falhou e não-
detectáveis, caso contrário. Falhas não-detectáveis podem ser subdivididas ainda em não-
observáveis, quando os demais processos não podem notar a ocorrência da falha (por exem-
plo, um processo faltoso informa um parâmetro fornecido pelo usuário incorretamente) e não-
diagnosticáveis, quando não é possível identificar o processo que gerou a falha (por exemplo,
os processos recebem uma mensagem não assinada).
As falhas detectáveis são classificadas em falhas por omissão e por comissão, sendo análo-
gas às falhas de progresso e segurança definidas em (BALDONI; HÉLARY; PIERGIOVANNI,
2007), respectivamente. Falhas de progresso atrapalham a terminação da computação, uma vez
que o processo faltoso não envia mensagens requeridas por sua especificação ou as envia a ape-
nas parte dos processos do sistema, enquanto que as falhas de segurança violam propriedades
invariantes às quais os processos devem atender. Falhas por comissão podem ser definidas como
o não-cumprimento de uma das seguintes restrições:
• Um processo deve enviar as mesmas mensagens para todos os outros. Um processo fal-
24
Figura 2.2: Categorização das falhas bizantinas (KIHLSTROM; MOSER; MELLIAR-SMITH,2003)
toso poderia, portanto, enviar a mesma mensagem com valores distintos para processos
distintos.
• As mensagens enviadas devem estar de acordo com o algoritmo sendo executado.
2.3 SISTEMAS DISTRIBUÍDOS DINÂMICOS
Neste trabalho, considera-se um sistema distribuído dinâmico aquele cuja composição do
sistema é dinâmica durante a sua execução, devido à entrada e saída aleatória de processos.
Desta forma, os processos que o compõem não têm conhecimento dos demais componentes
(Π), nem da sua quantidade (n). Cada processo pi conhece apenas um subconjunto Πi ⊆ Π
da população dos nós1. Sistemas peer-to-peer (P2P), redes de sensores sem fio, redes móveis
auto-organizáveis (MANETs) e grades de computadores abertas são os principais representantes
desta classe de sistemas.
Sistemas distribuídos dinâmicos podem ser caracterizados pelas seguintes propriedades
(SENS et al., 2008):
1. Conhecimento parcial da composição do sistema: requisitos como larga escala do sis-
tema e uso de comunicação sem fio, associados à dinamicidade da população dos nós,
tornam inviável a suposição do conhecimento completo da composição da rede por cada
processo participante;
2. Alta imprevisibilidade nos tempos de transmissão das mensagens;
1Neste trabalho, os termos “nó” e “processo” serão utilizados indistintamente.
25
3. Conectividade parcial, isto é, cada nó está conectado diretamente a apenas parte da po-
pulação dos nós. Em uma rede sem fio, por exemplo, cada nó só se comunica diretamente
com os nós dentro do seu alcance de transmissão. A suposição de uma rede comple-
tamente conectada, comum na abordagem clássica de sistemas distribuídos, não é mais
adequada;
4. Mobilidade dos nós: os nós podem alterar sua localização, sem entretanto modificar sua
identidade ou estado interno, levando a mudanças na topologia da rede.
Algoritmos projetados para ambientes clássicos, que supõem uma rede com topologia es-
tática e conhecida, não são mais adequados nesta nova abordagem. São necessárias, portanto,
adaptações que levem em consideração as propriedades acima levantadas.
Algumas tentativas foram feitas no intuito de modelar o ambiente de um sistema dinâmico
(AGUILERA, 2004; MOSTEFAOUI et al., 2005). Não há ainda, no entanto, um consenso sobre
os modelos abordados na literatura. O modelo utilizado neste trabalho é apresentado na Seção
5.1.
26
3 PROBLEMA DO CONSENSO
O consenso (PEASE; SHOSTAK; LAMPORT, 1980) é um problema fundamental em sis-
temas distribuídos, uma vez que sumariza a necessidade recorrente de os processos obterem
acordo sobre determinada propriedade. Na prática, tal propriedade poderia ser, por exemplo, a
confirmação ou não de uma transação distribuída, ou a ordem em um seqüência de alterações
em um banco de dados distribuído.
Diversos outros problemas importantes, como a confirmação atômica não-bloqueante (non-
blocking atomic commitment), a difusão atômica (atomic broadcast) e a replicação de máquinas
de estados (state machine replication) são redutíveis ao consenso (HURFIN et al., 1999; MAR-
TIN; ALVISI, 2006), o que o caracteriza como um bloco básico na construção de algoritmos
tolerantes a faltas. Em (HURFIN et al., 1999), por exemplo, mostra-se como solucionar diversos
problemas de acordo através de um arcabouço (framework) composto por um algoritmo gené-
rico de consenso e funções instanciáveis em tempo de compilação, que agem como parâmetros
para o algoritmo.
Neste capítulo, define-se formalmente o consenso, incluindo algumas de suas variantes. Em
seguida, apresentam-se os paradigmas mais utilizados na sua solução.
3.1 DEFINIÇÃO
O problema do consenso consiste num acordo entre os processos sobre a escolha de um
valor v dentre um conjunto V (quando V = 0,1, denomina-se consenso binário (CORREIA;
VERÍSSIMO; NEVES, 2006)). Cada processo pi, i ∈ 1, . . . ,n, propõe um valor vi e, ao
término do consenso, todos os processos corretos devem ter decidido por um mesmo valor
v ∈ vi : i = 1..n, isto é, um dentre os valores propostos.
A definição clássica do problema para um modelo de falhas benignas pode ser especificada
formalmente através das seguintes propriedades1 (GREVE, 2005; MARTIN; ALVISI, 2006):
1A terminologia e a definição destas propriedades varia na literatura. Ver, por exemplo, a definição em (HAD-ZILACOS; TOUEG, 1993), na qual a propriedade de Validade, por exemplo, mistura aspectos da propriedade deTerminação.
27
• Terminação: em algum momento no futuro, todo processo correto decide por um valor
v ∈V ;
• Irrevogabilidade: uma vez que um processo tenha decido por um valor v, sua decisão não
poderá ser alterada;
• Acordo: todo processo correto decide pelo mesmo valor v;
• Integridade: cada processo decide no máximo uma vez;
• Validade: se algum processo correto decide por um valor v, então v foi proposto por
algum processo p ∈Π.
Algumas definições permitem ainda que um processo correto decida por um valor v =⊥ /∈V
(HADZILACOS; TOUEG, 1993), indicando que não houve consenso entre os processos.
Denomina-se a primeira propriedade como uma propriedade de progresso (liveness), isto é,
uma propriedade que requer que um predicado seja verdadeiro em algum momento no futuro.
As demais são propriedade de segurança (safety), pois requerem que determinado predicado
seja sempre verdadeiro (VERISSIMO; RODRIGUES, 2001).
A seguir apresentam-se algumas definições alternativas para o consenso.
3.1.1 CONSENSO BIZANTINO
Trata-se da variante do consenso num cenário em que os processos estão sujeitos a falhas
bizantinas. Nessa situação, adota-se a convenção de que, se p é um processo faltoso, “p propõe
v” é um predicado verdadeiro, qualquer que seja v ∈ V (HADZILACOS; TOUEG, 1993). De
outra forma, a propriedade de Validade definida anteriormente não faria sentido, uma vez que
um processo malicioso pode propor valores diferentes para processos diferentes.
Encontra-se na literatura, para o modelo bizantino, a propriedade de Validade substituída
por três propriedades (CORREIA; VERÍSSIMO; NEVES, 2006):
• Validade 1 (similar à definida anteriormente): se algum processo decide por um valor v,
então v foi proposto por algum processo p ∈Π ou v =⊥ /∈V ;
• Validade 2: se todos os processos corretos propõem v, todos os processos corretos em
algum momento no futuro decidem por v. Esta propriedade é também denominada de
validade forte, sendo o consenso resultante denominado consenso forte (BALDONI et
al., 1999);
28
• Validade 3: se um valor v é proposto apenas por processos faltosos (corruptos), nenhum
processo correto decide por v.
As propriedades de Validade 2 e Validade 3 são definidas na tentativa de impedir que os
processos faltosos influenciem os corretos a tomarem uma decisão indesejada (LAMPORT;
SHOSTAK; PEASE, 1982; BALDONI et al., 1999), por exemplo, por um valor sem qualquer
conexão com os valores propostos pela aplicação que solicita o consenso. Esse objetivo, no
entanto, não é alcançado se nem todos os processos corretos propuserem o mesmo valor v; os
processos maliciosos podem, por exemplo, levar à decisão por um valor proposto pela minoria
dos processos corretos. Uma maneira de lidar com esta situação é a utilização de consenso
vetorial (ver Seção 3.1.3).
3.1.2 CONSENSO UNIFORME
Alterando-se as propriedades de Acordo e Validade da definição clássica, define-se con-
senso uniforme da seguinte forma (GREVE; TIXEUIL, 2007):
• Acordo Uniforme: se dois processos p,q∈Π (corretos ou não) decidem, respectivamente,
por vp,vq, então vp = vq;
• Validade uniforme: se algum processo p ∈ Π (correto ou não) decide por um valor v,
então v foi proposto por algum processo q ∈Π (ou, semelhantemente, v =⊥ /∈V ).
Estas propriedades especificam que os processos faltosos também devem atender a restri-
ções de segurança (safety). Assim, em alguns cenários, como em (CAVIN; SASSON; SCHI-
PER, 2005), pode-se resolver o consenso, mas não o consenso uniforme. O mesmo se aplica a
um contexto bizantino, já que, uma vez que os processos falham de maneira arbitrária (inclu-
sive maliciosamente), é impossível prover qualquer garantia a respeito do comportamento dos
processos faltosos.
3.1.3 OUTRAS DEFINIÇÕES
Diversas outras variantes do problema do consenso são encontradas na literatura. Destacam-
se ainda consenso vetorial (vector consensus) (DOUDOU; SCHIPER, 1998) e consenso apro-
ximado (HADZILACOS; TOUEG, 1993).
No consenso vetorial, os processos decidem sobre um vetor de n valores com pelo menos
f +1 entradas provenientes de processos corretos. Essa variante é utilizada especificamente no
29
modelo bizantino, por permitir que os processos avaliem a relevância de cada entrada do vetor.
Outra vantagem em relação ao consenso forte é que alguns problemas de acordo, como a difusão
atômica, podem ser reduzidos ao consenso vetorial, mas não ao consenso forte (BALDONI et
al., 1999).
Já no consenso aproximado, é requerido que os processos decidam por valores em V que
difiram entre si em no máximo ε , sendo ε > 0 uma constante de tolerância pré-definida. Isto é:
∀p,q ∈Π, p 6= q : (p decide por vp)∧ (q decide por vq)⇒ vp,vq ∈V ∧|vp− vq| ≤ ε
3.2 SOLUÇÕES EXISTENTES
Em um sistema completamente assíncrono, é impossível realizar consenso na ocorrência
de falhas, mesmo que um único processo falhe por colapso (FISCHER; LYNCH; PATERSON,
1985). Tal propriedade, conhecida como resultado ou impossibilidade FLP, impõe sérias res-
trições ao desenvolvimento de algoritmos distribuídos. Diversos trabalhos, portanto, propõem
formas de contornar tal impossibilidade (CORREIA; VERÍSSIMO; NEVES, 2006):
1. Utilização de algoritmos probabilísticos: A impossibilidade FLP diz respeito a algo-
ritmos de consenso determinísticos. Uma solução é utilizar algoritmos probabilísticos
(HADZILACOS; TOUEG, 1993). Neste contexto, requer-se que alguma das proprie-
dades do consenso (geralmente a propriedade de terminação) seja satisfeita com uma
probabilidade determinada (CORREIA; VERÍSSIMO; NEVES, 2006).
2. Introdução de requisitos temporais ao sistema: Devido à impossibilidade FLP e à di-
ficuldade de prover um sistema completamente síncrono para qualquer contexto, uma
forma de resolver o consenso é a suposição de um sistema parcialmente síncrono (ver
Seção 2.1). Diversos trabalhos buscam então identificar os requisitos de sincronia míni-
mos necessários para resolver o consenso (DOLEV; DWORK; STOCKMEYER, 1987;
AGUILERA et al., 2006).
3. Adição de oráculos ao sistema: A adição de oráculos distribuídos, tais como os de-
tectores de falhas não confiáveis (CHANDRA; TOUEG, 1996) e o detector de líder
(AGUILERA et al., 2001), permite a resolução do consenso em sistemas assíncronos.
Obviamente, devido à impossibilidade FLP, é impossível implementá-los em sistemas to-
talmente assíncronos sem fazer suposições de sincronia adicionais sobre o sistema. No
entanto, sua elegância está em permitir a abstração da necessidade de sincronia durante o
desenvolvimento do algoritmo de consenso, ficando tal tratamento sob responsabilidade
30
do oráculo de detecção. Detectores de falhas são o foco deste trabalho, sendo abordados
em maior detalhe no Capítulo 4.
4. Alterações na definição do consenso: Variantes mais fracas do consenso, tal como o
consenso aproximado definido na Seção 3.1.3, podem ser resolvidas em sistemas com-
pletamente assíncronos (HADZILACOS; TOUEG, 1993).
3.3 LIMITES DE TOLERÂNCIA A FALTAS NA RESOLU-ÇÃO DO CONSENSO
Em (DWORK; LYNCH; STOCKMEYER, 1988), são apresentados os limites teóricos de
tolerância a faltas para resolução do consenso em diversas configurações. Os resultados estão
sumarizados na Tabela 3.1. Supõe-se uma composição de processos estática e conhecida.
Modelo de Canais eFalhas versus Canais Processos Processos
Sincronia Síncrono Assíncrono Parcialmente Parcialmente Parcialmentedo Sistema Síncronos Síncronos SíncronosParada ou f ∞ 2 f +1 2 f +1 fColapsoOmissão f ∞ 2 f +1 2 f +1 2 f +1
Bizantino com f ∞ 3 f +1 3 f +1 2 f +1Autenticação
Bizantino 3 f +1 ∞ 3 f +1 3 f +1 3 f +1
Tabela 3.1: Número mínimo de processos necessários para resolver consenso em sistemas está-ticos tolerando f processos faltosos (DWORK; LYNCH; STOCKMEYER, 1988)
Devido à impossibilidade FLP, não é possível tolerar faltas em um sistema completamente
assíncrono. Em um sistema completamente síncrono, é possível tolerar qualquer número de
faltas se os processos falharem por colapso ou omissão, ou ainda de forma arbitrária se houver
um mecanismo de autenticação de mensagens. No caso de falhas bizantinas, são necessários
3 f +1 processos para tolerar f processos faltosos.
Se os canais de comunicação são parcialmente síncronos, são necessários 2 f +1 processos
para tolerar f faltas; este número aumenta para 3 f +1 no caso de falhas bizantinas, mesmo com
autenticação de mensagens. O resultado se mantém sejam os processos síncronos ou parcial-
mente síncronos.
No caso de processos parcialmente síncronos e canais síncronos, se os processos falharem
por colapso, é possível tolerar qualquer número de falhas. Se as falhas forem por omissão ou
31
bizantinas com autenticação de mensagens, é possível tolerar f processos faltosos se o sistema
possuir 2 f +1 processos. Se os processos falharem de forma bizantina, são necessários 3 f +1
processos para tolerar f processos faltosos.
3.3.1 RESULTADOS PARA SISTEMAS DISTRIBUÍDOS DINÂMICOS
Em sistemas com composição de processos desconhecidas, a possibilidade de realização do
consenso está sujeita à sincronia do sistema, ao modelo de falhas e ao grau de conectividade do
grafo de conhecimento dos processos. Os resultados são sumarizados na Tabela 3.2.
Solução modelo de detector de k participantes conectividade sincronismofalhas participação no poço entre componentes
FT-CUP colapso OSR – 1 OSR + padrão assíncrono + P(CAVIN; SASSON; SCHIPER, 2005) de falhas
FT-CUP colapso k-OSR f +1 2 f +1 k caminhos disjuntos assíncrono + ♦S(GREVE; TIXEUIL, 2007) nos nósBFT-CUP com assinaturas bizantinas k-OSR 2 f +1 3 f +1 k caminhos disjuntos parcialmente(ALCHIERI et al., 2008) nos nós síncronoBFT-CUP sem assinaturas bizantinas k-OSR 3 f +1 3 f +1 k caminhos disjuntos parcialmente(ALCHIERI et al., 2008) nos nós síncrono
Tabela 3.2: Condições para realização do consenso em sistemas com participantes desconheci-dos (ALCHIERI et al., 2008) (adaptada)
Uma abstração proposta nos trabalhos de consenso com participantes desconhecidos é a de
detectores de participação, que consistem em oráculos distribuídos que informam aos processos
sobre o conjunto de nós conhecidos. Classes de detectores de participação são definidas em
função de propriedades do grafo direcionado resultante da relação de conhecimento entre os
nós.
Em (CAVIN; SASSON; SCHIPER, 2004), verifica-se que a condição mínima de conec-
tividade para a resolução do consenso em tais sistemas (denominado CUP - consenso com
participantes desconhecidos, do inglês Consensus with Unknown Participants) é a presença de
um detector de participação da classe OSR (One Sink Reducible - redutível a um único poço).
Um detector de participação da classe OSR é aquele cujo grafo de conhecimento G é redutível
a um único poço, isto é, G é conexo e o grafo direcionado acíclico obtido pela sua redução
aos componentes fortemente conexos possui um único poço (um poço é um vértice sem arestas
de saída). Nesse trabalho inicial não são abordadas, no entanto, as condições necessárias para
realizar consenso tolerante a faltas.
A versão tolerante a faltas do CUP (denominada FT-CUP, de fault-tolerant CUP - CUP tole-
rante a faltas) foi apresentada inicialmente em (CAVIN; SASSON; SCHIPER, 2005). Verificou-
se que se apenas a condição de conectividade mínima for satisfeita, é necessário enriquecer o
32
sistema com um detector perfeito (da classe P), que não comete erros e só pode ser implemen-
tado em um sistema completamente síncrono (ver Seção 4.1). Além disso, sob tais condições
não é possível resolver o consenso uniforme (ver Seção 3.1.2). Entretanto, qualquer número de
faltas é tolerado, desde que o grafo de conhecimento remanescente permaneça redutível a um
único poço.
Em (GREVE; TIXEUIL, 2007) são apresentados os requisitos de conectividade mínimos
necessários para resolver o consenso, inclusive na versão uniforme, em um sistema com restri-
ções de sincronia mais fracas, no qual seja possível implementar um detector de falhas da classe
♦S (ver definição na Seção 4.1). As condições verificadas sobre o grafo de conhecimento são:
• Conectividade;
• A redução às componentes k-fortemente conexas2 tem somente uma componente poço;
• Entre quaisquer duas componentes k-fortemente conexas G1 e G2, se existe um caminho
de G1 para G2, então existem k caminhos disjuntos nos nós de G1 para G2.
A classe de detectores de participação com tais propriedades é denominada k-OSR. Neste
caso, é possível tolerar até f faltas, desde que f < k < n e f < n/2.
No modelo de falhas bizantinas, o consenso em sistemas com participantes desconhecidos
(denominado BFT-CUP) pode ser resolvido sob as mesmas condições de conectividade defini-
das acima. É necessário ainda que 3 f < k < n (ou 2 f < k < n, se as mensagens forem assinadas)
e que a componente poço tenha pelo menos 3 f +1 processos (ALCHIERI et al., 2008).
2Um grafo G(V,E) é k-fortemente conexo se entre quaisquer dois vértices vi,v j ∈ V existem pelo menos kcaminhos de vi para v j disjuntos nos vértices.
33
4 DETECTORES DE FALHASNÃO-CONFIÁVEIS
Detectores de falhas (FD) não-confiáveis (CHANDRA; TOUEG, 1996) são oráculos dis-
tribuídos que fornecem “dicas” aos processos sobre a ocorrência de falhas no sistema. A cada
invocação, o FD retorna um conjunto com as identidades dos processos que suspeita de terem
falhado. O termo não-confiável refere-se ao fato de tais entidades poderem cometer erros, seja
por não detectar processos incorretos ou por suspeitar de processos corretos.
A garantia de determinadas propriedades sobre os erros que podem ser cometidos possibilita
a solução de diversos problemas, dentre eles o consenso. Os algoritmos de consenso que se
utilizam de tais abstrações são denominados indulgentes (GUERRAOUI; RAYNAL, 2004),
uma vez que os erros do detector de falhas não acarretam em desrespeito às propriedades de
segurança do consenso. Uma vez que a impossibilidade FLP diz respeito à incapacidade de
se distinguir, em um modelo de falhas por colapso, entre um processo faltoso e um processo
ou canal lento (GREVE, 2005), o uso de FDs simplifica o desenvolvimento de algoritmos de
consenso assíncronos. O detector de falhas isola o tratamento da detecção das falhas e das
necessidades de sincronia, provendo uma abstração ao algoritmo de tais requisitos.
A seguir definem-se as classes de detectores de falhas propostas por Chandra e Toueg
(CHANDRA; TOUEG, 1996). Na Seção 4.2, discutem-se implementações de tais oráculos.
Nas Seções 4.3 e 4.4, abordam-se, respectivamente, detectores de falhas bizantinas e detectores
de falhas adaptados para sistemas distribuídos dinâmicos.
4.1 DEFINIÇÃO
Em (CHANDRA; TOUEG, 1996), os detectores de falhas são definidos em função de duas
propriedades: uma de completude, que especifica a abrangência da detecção de falhas e outra
de precisão, que restringe os equívocos (detecção de processos corretos como estando faltosos)
cometidos pelo detector. As seguintes propriedades são definidas:
• Completude forte: existe um tempo após o qual todo processo correto suspeita perma-
34
nentemente de todo processo faltoso;
• Completude fraca: existe um tempo após o qual algum processo correto suspeita perma-
nentemente de todo processo faltoso;
• Precisão forte: nenhum processo é suspeito antes de falhar;
• Precisão fraca: existe um processo correto que nunca será suspeito;
• Precisão forte após um tempo: em algum momento no futuro, todo processo correto
não será suspeito por qualquer processo;
• Precisão fraca após um tempo: em algum momento no futuro, um processo correto não
será suspeito por qualquer processo.
A combinação das diferentes propriedades de completude e precisão define oito classes de
detectores de falhas, apresentadas na Tabela 4.1.
PrecisãoCompletude Forte Fraca Forte após um tempo Fraca após um tempo
Forte Perfeito Forte Perfeito Forte(P) (S ) Após um Tempo Após um Tempo
(♦P) (♦S )Fraca Quase-perfeito Fraco Quase-perfeito Fraco
(Q) (W ) Após um Tempo Após um Tempo(♦Q) (♦W )
Tabela 4.1: Classes de detectores de falhas obtidas pela combinação das propriedades de com-pletude e precisão (CHANDRA; TOUEG, 1996)
A classe de detectores de falhas P , que não comete erros, só pode ser implementada em um
sistema completamente síncrono. A classe ♦W , que provê completude fraca e precisão fraca
após um tempo consiste na classe mais fraca de detectores de falhas na qual é possível reali-
zar consenso num sistema com processos conhecidos (CHANDRA; HADZILACOS; TOUEG,
1996). Em (CHANDRA; TOUEG, 1996) mostra-se como resolver consenso utilizando detec-
tores de falhas das classes S e ♦S (completude forte e precisão fraca e fraca após um tempo,
respectivamente), desde que exista uma maioria de processos corretos no sistema. Mostra-se
também a equivalência entre as classes de detectores com completude forte e completude fraca.
Este trabalho terá seu foco nos detectores de falhas da classe ♦S , por serem, juntamente
com os da classe ♦W , aqueles que requerem a sincronia mínima necessária para resolver o
consenso assíncrono.
35
4.1.1 DETECÇÃO DE LÍDER
Complementar à abstração dos detectores de falhas, define-se o oráculo distribuído de de-
tecção de líder, denominado Ω (Ômega) (CHANDRA; HADZILACOS; TOUEG, 1996). Tal
detector obedece à seguinte propriedade:
• Liderança após um tempo: Existe um tempo após o qual todo processo correto confia no
mesmo processo correto.
Trabalhos que propõem protocolos eficientes de detecção de líder incluem (AGUILERA et
al., 2001; MOSTEFAOUI; RAYNAL; TRAVERS, 2004; FERNÁNDEZ; JIMÉNEZ; RAYNAL,
2006; RAYNAL, 2007). Este último provê uma visão geral (survey) sobre o assunto. Em (JIMÉ-
NEZ; ARÉVALO; FERNÁNDEZ, 2006) é proposto um protocolo que suporta uma população
de nós com participação desconhecida, sendo portanto adequado para sistemas dinâmicos sem
mobilidade. Um resultado importante é que, embora em sistemas com participação conhecida
as classes de detectores ♦S e Ω sejam equivalentes (CHANDRA; HADZILACOS; TOUEG,
1996; MOSTEFAOUI et al., 2006), o mesmo não é válido para uma população desconhecida.
Dentre os trabalhos que propõem resolver consenso utilizando uma abstração de detecção
de líder como base, destaca-se o algoritmo Paxos de Lamport (LAMPORT, 1998). Outro tra-
balho neste sentido é (MOSTEFAOUI; RAYNAL, 2001). Além disso, pode-se também utilizar
detecção de líder para melhorar a eficiência da solução de um conjunto de tarefas distribuídas
(AGUILERA et al., 2001).
4.2 DETECTORES DE FALHAS POR COLAPSO
Diversos trabalhos propõem implementações eficientes de detectores de falhas em sistemas
sujeitos a falhas por colapso. A maioria deles baseia-se no uso de mensagens do tipo “eu es-
tou vivo” (I’m alive) enviadas aos processos vizinhos (LARREA; FERNÁNDEZ; ARÉVALO,
2000; FERNÁNDEZ; JIMÉNEZ; ARÉVALO, 2006). Se um processo demora de enviar um
sinal de vida, um temporizador (timeout) estabelecido pelos seus vizinhos irá expirar, levando
à sua suspeita. Se futuramente o processo responder corretamente, o valor do seu temporiza-
dor será acrescido, de forma a evitar suspeitas incorretas. Em (MOSTEFAOUI; MOURGAYA;
RAYNAL, 2003), foram propostos detectores de falhas assíncronos, que não se baseiam no
uso de temporizadores, mas no padrão de troca de mensagens e na quantidade de falhas f e de
processos n no sistema.
36
As técnicas utilizadas para implementar os detectores de falhas em ambientes de falhas
por colapso não são adequadas, no entanto, para o modelo de falhas bizantinas. Um processo
malicioso pode responder corretamente às requisições do detector de falhas, sem nunca ser
suspeito e no entanto não colaborar para o progresso do algoritmo que usa o detector como
módulo subjacente. A seguir descrevem-se abordagens para contornar tal situação.
4.3 DETECTORES DE FALHAS BIZANTINAS
Os primeiros trabalhos a proporem detectores de falhas para o modelo de falhas bizantinas
foram (MALKHI; REITER, 1997; DOUDOU; SCHIPER, 1998). No entanto, tais detectores
apenas lidam com falhas de progresso (omissão) (ver Seção 2.2.3). As falhas de segurança
(comissão) são detectadas pelo algoritmo de consenso.
Em (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003) procura-se detectar o máximo de
falhas bizantinas possível. Segundo a caracterização de falhas bizantinas proposta pelos autores
(ver Seção 2.2.3), tratam-se as falhas detectáveis (tanto de progresso quanto de segurança).
Uma vez que as falhas bizantinas são definidas como desvio de comportamento em relação
à especificação do algoritmo sendo executado, o detector de falhas é definido em função do
algoritmo que o utiliza.
Baldoni et al. (BALDONI; HÉLARY; PIERGIOVANNI, 2007) definem uma arquitetura
de detectores de falhas em que é possível adaptar com poucas alterações qualquer algoritmo
tolerante a falhas por colapso em um equivalente tolerante a falhas bizantinas. Para tanto, a
detecção das falhas é distribuída entre dois componentes: um detector de falhas de progresso,
consistindo num detector de mutismo (muteness detectors) (DOUDOU; SCHIPER, 1998) e um
detector de falhas de segurança. Este último é composto por um módulo de assinaturas, um mó-
dulo de certificação e outro consistindo numa máquina de estados em que os processos modelam
o comportamento de cada um dos seus vizinhos, de forma a detectar desvios de comportamento.
Apesar de o modelo de Baldoni et al. modelar o tratamento de falhas bizantinas de forma
mais modular e genérica, por simplicidade será utilizado como base para o detector de falhas
aqui proposto o trabalho de Kihlstrom et al..
37
4.3.1 DETECTORES DE FALHAS BIZANTINAS SEGUNDO KIHLS-TROM ET AL.
Num sistema sujeito a falhas bizantinas, não é possível detectar todos os tipos de falha que
podem ocorrer (ver Seção 2.2.3). Assim, a propriedade de completude forte é redefinida para o
modelo de falhas bizantinas como sendo (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003):
• Completude forte bizantina (para um algoritmo A ): em algum momento no futuro
todo processo correto suspeita permanentemente de todo processo que se desviou de A
de forma detectável.
Em (CHANDRA; TOUEG, 1996), supondo canais confiáveis e que os processos falhem
por colapso, mostra-se como transformar qualquer detector de falhas D que atenda à proprie-
dade de completude fraca em um detector de falhas correspondente D ′ que atenda à completude
forte, de uma tal forma que a propriedade de precisão atendida por D é preservada em D ′. No
entanto, adaptando-se a propriedade de completude fraca para o modelo bizantino de forma
similar à acima proposta, a transformação definida em (CHANDRA; TOUEG, 1996) aplicada
a um detector de falhas D com completude fraca bizantina resultaria num detector de falhas
D ′ com completude forte bizantina, mas não necessariamente preservaria em D ′ a proprie-
dade de precisão atendida por D (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003). Dessa
forma, define-se adicionalmente para o modelo bizantino a seguinte propriedade de completude
(KIHLSTROM; MOSER; MELLIAR-SMITH, 2003):
• Completude (k + 1)-fraca bizantina (para um algoritmo A ): em algum momento no
futuro pelo menos k+1 processos corretos suspeitam permanentemente de todo processo
que se desviou de A de forma detectável.
Listam-se na Tabela 4.2 as possíveis classes de detectores de falhas bizantinos utilizando as
propriedades de completude forte bizantina, completude (k +1)-fraca bizantina, precisão forte
após um tempo e precisão fraca após um tempo.
(KIHLSTROM; MOSER; MELLIAR-SMITH, 2003) mostra então como resolver consenso
utilizando um detector de falhas da classe ♦W (Byz,A ). São exibidos os algoritmos para de-
tectores da classe ♦P(Byz,A ). Mostra-se também como transformar um detector da classe
♦W (Byz,A ) em outro da classe ♦S (Byz,A ). Note-se que o detector de falhas é definido em
função do algoritmo que o utiliza.
38
PrecisãoCompletude para
o algoritmo A Forte após um tempo Fraca após um tempoForte bizantina Perfeito Após um Forte Após um
Tempo (♦P(Byz,A )) Tempo (♦S (Byz,A ))(k +1)-fraca bizantina Quase-perfeito Após Fraco Após um
um Tempo (♦Q(Byz,A )) Tempo (♦W (Byz,A ))
Tabela 4.2: Classes de detectores de falhas bizantinas (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003)
IMPLEMENTAÇÃO
A implementação de detectores de falhas bizantinas de (KIHLSTROM; MOSER; MELLIAR-
SMITH, 2003) consiste no monitoramento das mensagens recebidas dos processos vizinhos.
Quando o algoritmo A especifica que uma mensagem m deve ser enviada por um processo p,
os demais processos estabelecem um temporizador para a mensagem. Se m não for recebida
por q, q suspeita de p. Se futuramente m chegar, a suspeita é revogada; mantém-se, portanto,
uma lista de mensagens aguardadas para cada processo suspeito.
As mensagens recebidas são verificadas quanto a seus certificados e à coerência com as
mensagens recebidas pelos demais processos. Caso se verifique uma falha de comissão, o
processo que a causou é marcado como bizantino, sendo suspeito de forma permanente.
4.4 DETECTORES DE FALHAS COM PARTICIPANTESDESCONHECIDOS
Trabalhos que propõem detectores de falhas por colapso para populações dinâmicas e par-
cialmente conhecidas incluem (LARREA; FERNÁNDEZ; ARÉVALO, 2000; GUPTA; CHAN-
DRA; GOLDSZMIDT, 2001). Em (FRIEDMAN; TCHARNY, 2005) apresentam-se detectores
tolerantes à mobilidade dos nós. Todos estes baseiam-se, no entanto, no uso de temporizadores
(timeouts), o que não é adequado para redes com alta instabilidade, características de sistemas
dinâmicos (SENS et al., 2008).
O trabalho (SENS et al., 2008) destaca-se por propor uma implementação assíncrona de
detectores de falhas para populações dinâmicas. Utiliza-se, ao invés de mensagens do tipo “eu
estou vivo” temporizadas, um mecanismo de perguntas e respostas (query/response). Garante-
se que, se o sistema atender a determinadas propriedades comportamentais, as falhas dos pro-
cessos serão detectadas. Com pequenas alterações adicionais, mostra-se ser possível tolerar a
39
existência de nós móveis. O mesmo é descrito em maiores detalhes na Seção 5.2.
Segundo o conhecimento dos autores, o detector proposto neste trabalho (Capítulo 5) é o
primeiro detector de falhas bizantinas em sistemas dinâmicos a ser desenvolvido, como uma
extensão de (SENS et al., 2008). É apresentado um detector da classe ♦S (Byz,A ), sendo A
o algoritmo que utiliza o detector de falhas. Assim como em (SENS et al., 2008), o protocolo
proposto é assíncrono. Não foi modelada, no entanto, a tolerância à mobilidade dos nós, embora
se acredite ser simples, sendo proposta como trabalho futuro.
No Capítulo 5 são apresentados o modelo de comunicação que acredita-se ser necessário
para a detecção assíncrona de falhas bizantinas, os requisitos de conectividade do grafo de
conhecimento e o algoritmo de detecção de falhas bizantinas.
40
5 DETECTOR ASSÍNCRONO DEFALHAS BIZANTINAS COMPARTICIPANTESDESCONHECIDOS
Este capítulo descreve um protocolo assíncrono de detecção de falhas bizantinas da classe
♦S (Byz,A ) para sistemas com uma população dinâmica e desconhecida. Na Seção 5.1
descreve-se o modelo de sistema. A Seção 5.2 apresenta o funcionamento do protocolo de
(SENS et al., 2008), utilizado como base para o trabalho proposto, cujo funcionamento é des-
crito na Seção 5.3. A Seção 5.4 define as propriedades comportamentais que o sistema deve
atender para que o protocolo funcione corretamente. A Seção 5.5 apresenta um algoritmo que
implementa o detector de falhas proposto, sendo um esboço de prova da sua corretude exibido
na Seção 5.6. Não são apresentadas as provas formais, ficando indicadas como trabalho futuro.
5.1 MODELO DE SISTEMA
Supõe-se um sistema distribuído composto por um conjunto Π = p1, p2, . . . , pn com n > 4
processos. Não são feitas quaisquer restrições sobre a velocidade dos processadores, sobre o
desvio relativo dos relógios ou sobre os atrasos de transmissão das mensagens; isto é, supõe-se
um sistema assíncrono. Supõe-se a ocorrência de falhas bizantinas e a existência de um meca-
nismo de autenticação de mensagens. Os processos não têm conhecimento de Π ou n, apenas
de um subconjunto de Π com os quais estabeleceram comunicação anteriormente. O número
máximo de falhas tolerado f é conhecido por todos os processos. Supõe-se, para simplifica-
ção das definições apresentadas, a existência de um tempo global t, embora o mesmo não seja
conhecido pelos processos.
Cada processo é identificado unicamente e processos faltosos não podem obter mais de
um identificador, de forma que é impossível a ocorrência de ataques sybil (DOUCEUR, 2002).
Um ataque sybil consiste na obtenção por um processo malicioso de diversas identidades. Tal
41
processo, então, simularia uma maioria no sistema e controlaria sua execução.
Os processos trocam mensagens por difusão (broadcast) através de uma rede de comunica-
ção sem fio. Supõe-se a existência de canais confiáveis, de forma que as mensagens difundidas
são recebidas em algum momento no futuro por todos os processos dentro da área de cobertura
(range) do transmissor que não falharem. Na Figura 5.1, destaca-se a área de cobertura de dois
processos em uma rede de comunicação sem fio. Os canais são confiáveis, isto é, não dupli-
cam, alteram ou inserem novas mensagens e todo processo correto autentica suas mensagens de
forma incorruptível.
Figura 5.1: Área de cobertura em uma rede de comunicação sem fio
O sistema pode ser representado por um grafo não-direcionado G(V,E), sendo V = Π e
(pi, p j) ∈ E se pi e p j encontram-se no range um do outro (pi e p j são denominados vizinhos).
A Figura 5.2 exibe uma possível representação da rede de comunicação da Figura 5.1 através
de um grafo.
Adotam-se neste trabalho as definições de range (ou área de cobertura de difusão), densi-
dade da área de cobertura e rede com f -cobertura propostas em (SENS et al., 2008):
Definição 1 (Área de cobertura de difusão (range)) Seja G(V,E) o grafo de comunicação de
uma rede. A área de cobertura rangei de um nó pi é definida pelo conjunto:
rangei := pi∪p j ∈Π : (pi, p j) ∈ E
Isto é, rangei consiste nos vizinhos de pi, além de pi. Note-se que |rangei| equivale ao grau
de pi em G mais 1 e que pi ∈ range j⇔ p j ∈ rangei. Ou seja, a comunicação entre os processos
é simétrica.
42
Figura 5.2: Grafo de comunicação para a rede da Figura 5.1
Definição 2 (Densidade da área de cobertura) A densidade da área de cobertura d de uma
rede com grafo de comunicação G(V,E) consiste no tamanho do menor range da rede, isto é:
d := min |rangei| : i ∈ 1,2, ...,n
d é portanto o grau mínimo do grafo somado a 1. Considera-se que o parâmetro d da rede
é conhecido por todos os processos.
Definição 3 (Rede com f -cobertura) Uma rede de comunicação representada pelo grafo G(V,E)
tem f -cobertura se e somente se G é ( f +1)-conexo.
Define-se adicionalmente neste trabalho f -cobertura bizantina:
Definição 4 (Rede com f -cobertura bizantina) Uma rede de comunicação representada pelo
grafo G(V,E) tem f -cobertura bizantina se e somente se G é (2 f +1)-conexo.
Exibe-se na Figura 5.3 o grafo de uma rede com f -cobertura bizantina, supondo f = 1.
Um grafo k-conexo possui k caminhos distintos nos vértices entre qualquer par de vértices
(BONDY; MURTY, 1976), o que leva à seguinte observação:
Observação 1 Em uma rede com f -cobertura bizantina, apesar da ocorrência de f < n falhas,
existirão pelo menos f +1 caminhos distintos entre cada par de nós.
De forma similar ao apontado em (SENS et al., 2008), verifica-se que uma rede com f -
cobertura bizantina apresenta d > 2 f +1 .
43
Figura 5.3: Grafo de uma rede com f -cobertura bizantina ( f = 1)
5.2 FUNCIONAMENTO DO DETECTOR DE FALHAS PORCOLAPSO DE SENS ET AL.
Em (SENS et al., 2008), obtém-se um protocolo assíncrono de detecção de falhas por co-
lapso por meio de um mecanismo de perguntas e respostas (mensagens do tipo QUERY/RE-
SPONSE), executado em rodadas assíncronas, ilustrado na Figura 5.4. Os processos mantêm
internamente conjuntos de suspeitas (suspected) e equívocos (mistake), que são incluídos nas
mensagens QUERY e RESPONSE e atualizados na recepção das mesmas. Cada suspeita ou equí-
voco é etiquetado com um relógio lógico (LAMPORT, 1978), de forma que os processos utili-
zam apenas a informação mais recente.
Figura 5.4: Funcionamento do mecanismo de query/response proposto em (SENS et al., 2008)(d = 5, f = 1)
A cada rodada, um processo que não falhou envia uma mensagem QUERY a seus vizi-
nhos. Ao receber uma mensagem QUERY, confirma-se a recepção enviando uma mensagem
44
RESPONSE ao remetente. O processo que enviou a mensagem QUERY espera então receber
mensagens RESPONSE de pelo menos d− f processos, incluindo a si mesmo. A suposição de
uma rede com f -cobertura garante a recepção de um tal número de mensagens RESPONSE. O
processo que enviou a mensagem QUERY suspeita então dos nós que não enviaram uma men-
sagem RESPONSE (cada par QUERY-RESPONSE é identificado unicamente). Ao receber uma
mensagem QUERY com uma suspeita sobre si mesmo, um processo inclui um equívoco mais
recente que a suspeita em seu conjunto mistake. O mecanismo de QUERY/RESPONSE garante a
difusão das suspeitas e equívocos por toda a rede, de forma que o detector de falhas resultante
atende às propriedades de completude forte e precisão fraca após um tempo (classe ♦S ).
A corretude do protocolo (em relação às propriedades da classe ♦S ) é garantida caso o
sistema atenda a determinadas propriedades comportamentais. A primeira, denominada propri-
edade de inclusão, deve ser respeitada por todos os processos e é definida como:
Propriedade 1 (Propriedade de Inclusão (MP)) Seja t um instante de tempo e Kti o con-
junto de processos que receberam uma mensagem QUERY de pi até o instante t. Um processo
pi satisfaz a propriedade de inclusão se:
MP(pi) := ∃t ≥ 0 : |Kti |> f +1
Além disso, para garantir a precisão forte após um tempo, um processo correto deve atender
à propriedade de receptividade, definida como:
Propriedade 2 (Propriedade de Receptividade (RP)) Sejam t e u instantes de tempo e seja
rec_ f romtj o conjunto de pelo menos d− f processos dos quais p j recebeu respostas à mensa-
gem QUERY que terminou antes ou no instante t. A propriedade RP do processo correto pi é
definida como:
RP(pi) := ∃u : ∀t > u,∀p j ∈ rangei, pi ∈ rec_ f romtj
O mecanismo de tolerância à mobilidade descrito em (SENS et al., 2008), no entanto, não
é abordado aqui. O leitor interessado deve referir-se ao texto original.
5.3 FUNCIONAMENTO DO PROTOCOLO PROPOSTO
Tendo em vista a possível ocorrência de processos maliciosos, o uso de mecanismos como
mensagens do tipo “eu estou vivo” não são suficientes para a detecção de falhas em um modelo
45
Figura 5.5: Mecanismo de espera de mensagens do protocolo proposto (d = 5, f = 1)
bizantino. Um processo faltoso pode responder corretamente às mensagens do detector de falhas
sem no entanto garantir o progresso e a segurança do algoritmo sendo executado. Conseqüente-
mente, a detecção das falhas deve se basear no padrão das mensagens enviadas na execução do
algoritmo A que utiliza o detector de falhas. Assim sendo, de forma similar a (KIHLSTROM;
MOSER; MELLIAR-SMITH, 2003), as suspeitas são levantadas em função das mensagens re-
queridas por A . O detector em (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003) baseia-se,
entretanto, no uso de temporizadores para detectar falhas de omissão.
Neste trabalho, de forma semelhante ao proposto em (SENS et al., 2008) (ver Seção 5.2), a
detecção assíncrona das falhas é feita aguardando-se a recepção de determinada mensagem de
d− f remetentes distintos. Entretanto, semelhantemente ao mecanismo de mensagens do tipo
“eu estou vivo” (I’m alive), o padrão de mensagens QUERY-RESPONSE no qual (SENS et al.,
2008) se fundamenta não é adequado ao modelo bizantino, pois um processo faltoso pode en-
viar mensagens RESPONSE sem no entanto atender aos requisitos de progresso de A . Propõe-se
aqui, portanto, que os processos aguardem a recepção das mensagens requeridas por A a partir
de pelo menos (d− f ) remetentes distintos, suspeitando-se de omissão dos demais processos
(ver Figura 5.5). Isso leva ao requisito de que o padrão de comunicação do algoritmo A seja
distribuído (ou seja, n→ n), isto é, que a cada passo todos os processos troquem mensagens en-
tre si. Um algoritmo de consenso desse tipo que utiliza um detector de falhas ♦S é apresentado
em (GUERRAOUI; RAYNAL, 2004).
Com base nessa consideração, conjectura-se ser impossível realizar a detecção de falhas por
omissão, caso o padrão de troca de mensagens seja do tipo 1→ n, pois nesse caso não haveria
como diferenciar uma falha por omissão de um retardo na recepção da mensagem, pelo fato de
o sistema ser assíncrono. Portanto, conjectura-se que:
46
Conjectura 1 É impossível detectar falhas bizantinas de forma assíncrona caso o padrão de
troca de mensagens seja do tipo 1 → n, isto é, se em determinado momento, o algoritmo
A determina que apenas um processo envia mensagens aos demais (n).
Cada suspeita (suspicion) sobre um processo pi é associada a uma mensagem m requerida
por A (requer-se, portanto, que as mensagens recebam identificadores únicos). As suspeitas
são propagadas na rede e um processo correto adotará uma suspeita não gerada por ele próprio
se e somente se receber f +1 ocorrências devidamente autenticadas provenientes de processos
distintos (o requisito de f +1 ocorrências impede que processos maliciosos imponham suspei-
tas sobre processos corretos; ver Figura 5.6). Se em algum momento um processo correto p j
receber m de pi, declarará um equívoco (mistake) sobre a suspeita e difundirá a mensagem m
aos demais, a fim de que façam o mesmo (ver Figura 5.7). Este procedimento permite que
um processo malicioso, de forma intermitente, provoque uma suspeita e em seguida a revo-
gue, levando-se a um mascaramento de parte das falhas por omissão e a uma degradação do
desempenho do detector de falhas. Não é possível, no entanto, distinguir um processo com este
comportamento de um processo lento ou de um período de instabilidade no canal de comunica-
ção. Esta forma de geração de equívocos difere da apresentada em (SENS et al., 2008), na qual
o próprio processo suspeito gera um equívoco.
Figura 5.6: Geração de suspeitas no protocolo proposto ( f = 1)
Para ser possível a detecção das falhas de comissão, um formato de mensagens deve ser
estabelecido. Cada mensagem deve também incluir um certificado que possibilite aos demais
processos verificar a coerência da mesma com o algoritmo A . Caso um processo detecte a
invalidade de uma mensagem recebida, seja por não atender ao formato ou por não estar devi-
47
Figura 5.7: Geração de equívocos no protocolo proposto ( f = 1)
damente justificada, suspeitará permanentemente do processo remetente e encaminhará a men-
sagem original aos demais processos, de forma que a suspeita seja propagada (ver Figura 5.8).
O detector, portanto, não comete erros na detecção das falhas por comissão. Mensagens que
não estejam devidamente autenticadas são descartadas, uma vez que configuram uma falha não-
diagnosticável (ver Seção 2.2.3). Entretanto, se uma mensagem re-encaminhada (como prova
de uma falha por comissão ou de um equívoco) não estiver assinada, suspeita-se de comissão do
processo que a reencaminhou. Note-se que suspeitas, equívocos e provas de falhas por comissão
são todos encaminhados através de uma única mensagem do tipo SUSPICION.
Figura 5.8: Detecção de falhas por comissão no protocolo proposto ( f = 1)
Em (KIHLSTROM; MOSER; MELLIAR-SMITH, 2003), adicionalmente, é possível de-
48
tectar quando um processo encaminha duas versões diferentes da mesma mensagem, como a
situação ilustrada na Figura 5.9. Para isto requer-se que os processos corretos reencaminhem
para todos os demais cada mensagem recebida, além de que seja gerado um histórico das men-
sagens provenientes de cada processo. Supõe-se no entanto que os processos podem realizar
comunicação entre pares. No modelo aqui proposto, em que os processos se comunicam apenas
por difusão local em canais confiáveis, é natural supor que uma mensagem transmitida será re-
cebida com conteúdo idêntico por todos os processos corretos, de forma que este tipo de falhas
não pode ocorrer. Chega-se portanto à seguinte observação:
Observação 2 Em um ambiente de falhas bizantinas, a suposição de comunicação apenas por
difusão simplifica o tratamento das falhas por comissão, uma vez que os processos vizinhos do
remetente têm uma visão consistente das mensagens enviadas pelo mesmo.
Figura 5.9: Processo corrupto que envia mensagens com valores diferentes para processos dife-rentes (supor x 6= y, y 6= z ou x 6= z)
Não foi realizada uma análise da complexidade do protocolo, em relação ao número de
mensagens transmitidas pelos processos, sendo indicada como trabalho futuro. Numa análise
superficial, verifica-se que em uma rede de larga escala, a difusão por toda a rede das infor-
mações de suspeitas, equívocos e de provas de comportamento comissivo pode dificultar a es-
calabilidade do sistema. No entanto, essa propagação é necessária para garantir a validade da
propriedade de completude forte bizantina do detector ♦S (Byz,A ).
5.4 PROPRIEDADES COMPORTAMENTAIS
Para que o protocolo proposto neste trabalho funcione corretamente, é necessário que os
processos atendam à propriedade de inclusão bizantina, definida como:
49
Figura 5.10: Inclusão de um processo novo no sistema com base na propriedade ByzMP( f = 1)
Propriedade 3 (Propriedade de Inclusão Bizantina (ByzMP)) Seja t um instante de tempo
e KBti o conjunto de processos que receberam uma mensagem SUSPICION de pi até o instante
t. Um processo pi satisfaz a propriedade de inclusão bizantina se:
ByzMP(pi) := ∃t ≥ 0 : |KBti|> 2 f +1
Esta propriedade garante que um processo novo pi no sistema em algum momento no futuro
será conhecido por pelo menos 2 f + 1 processos, dos quais pelo menos f + 1 serão corretos.
Para tanto, é necessário que pi se comunique com pelo menos 2 f + 1 processos dentro de sua
área de cobertura, enviando-lhes uma mensagem SUSPICION por difusão. Dessa forma, se pi
falhar, em algum momento no futuro pelo menos f + 1 processos corretos suspeitarão de pi e
transmitirão a suspeita para o restante do sistema, de forma que a propriedade de completude
forte bizantina do detector ♦S (Byz,A ) seja atendida. Se um processo novo não se comunicar
com nenhum outro, é impossível atender à propriedade de completude fraca (FERNÁNDEZ;
JIMÉNEZ; ARÉVALO, 2006). A inclusão de um processo novo no sistema com base nessa
propriedade é ilustrada na Figura 5.10.
Para que a propriedade de precisão fraca após um tempo da classe ♦S (Byz,A ) seja ante-
dida, é necessário que exista um processo correto cujas mensagens a partir de algum momento
estejam sempre entre as d− f primeiras recebidas pelos seus vizinhos, a cada requisição de A .
Assim sendo, após um tempo pi não será mais suspeito por nenhum processo e terá quaisquer
suspeitas anteriores revogadas através de equívocos. Logo, a rede deve possuir um nó correto
que atenda à propriedade de receptividade bizantina, definida como:
Propriedade 4 (Propriedade de Receptividade Bizantina (ByzRP)) Sejam t e u instantes
de tempo e seja byz_rec_ f romtj o conjunto de pelo menos d− f processos dos quais p j recebeu
50
Figura 5.11: Comportamento de um processo que atende à propriedade ByzRP (d = 4, f = 1)
a mensagem requerida por A no passo em execução no instante t. A propriedade ByzRP do
processo correto pi é definida como:
ByzRP(pi) := ∃u : ∀t > u,∀p j ∈ rangei, pi ∈ byz_rec_ f romtj
Na Figura 5.11, ilustra-se o comportamento de um processo que atende a tal propriedade.
5.5 IMPLEMENTAÇÃO
Os Algoritmos 1-3 implementam um detector de falhas da classe ♦S (Byz,A ), desde que
a rede atenda às propriedades de f -cobertura bizantina, inclusão bizantina e receptividade bi-
zantina descritas anteriormente. Cada processo executa quatro tarefas em paralelo: T1, à qual
as requisições do algoritmo A são feitas, responsável pela geração de novas suspeitas; T2, res-
ponsável pela recepção de mensagens de processos lentos e conseqüente geração de equívocos;
T3, responsável pela divulgação das suspeitas internas e externas, dos equívocos e das provas
de comportamento comissivo, através de mensagens SUSPICION; T4, responsável pela atualiza-
ção do estado interno do processo durante a recepção de mensagens SUSPICION. As variáveis
utilizadas por cada processo pi são descritas a seguir:
• out puti: armazena a saída do detector de falhas, isto é, o conjunto de identificadores dos
processos de que pi suspeita terem falhado;
• knowni: armazena o conjunto dos processos que se comunicaram com pi, isto é, sua
suposta vizinhança. É atualizada a cada recepção de mensagem m, seja m do tipo SUSPI-
CION ou uma mensagem inerente a A ;
51
• changed_state: variável booleana que indica que houve mudança no estado interno do
processo; utilizada para otimizar o envio de mensagens SUSPICION. É inicializada com
true para que, ao se integrar ao sistema, um processo novo difunda uma mensagem SUS-
PICION à sua vizinhança;
• external_suspi: matriz que armazena suspeitas externas (geradas por outros processos).
A matriz é indexada por um identificador de processo q e por um identificador de mensa-
gem idm. Cada entrada armazena o conjunto de processos dos quais pi recebeu suspeitas
de q não ter enviado a mensagem com identificador idm;
• internal_suspi: vetor de suspeitas internas. Uma suspeita interna é gerada pela não-
recepção de uma mensagem requerida por A ou pela existência de pelo menos f + 1
suspeitas externas sobre um mesmo par processo-mensagem;
• mistakei: vetor que armazena, para cada processo aplicável p j, o conjunto de equívo-
cos relacionados a p j, na forma de mensagens requeridas por A sobre as quais foram
levantadas suspeitas;
• byzantinei: conjunto de tuplas do tipo 〈processo, mensagem〉 que provam comportamento
bizantino do processo associado. A notação 〈p,−〉 indica “qualquer tupla associada ao
processo p”;
• rec_ f romi: conjunto de processos dos quais pi recebeu a mensagem requisitada por A ;
• byzantine: variável booleana utilizado pela tarefa T4 para verificar se o processo que
enviou a mensagem SUSPICION apresentou comportamento bizantino.
Supõe-se ainda a existência das seguintes primitivas:
• m.id - retorna o identificador da mensagem m;
• message(idm) - retorna a mensagem associada ao identificador idm;
• verificação de boa-formação, justificação (certificação do conteúdo) e autenticação das
mensagens;
• requisição por A de uma determinada mensagem;
• broadcast m - difunde a mensagem m para os vizinhos de pi;
• eval(pr) - avalia e executa uma chamada de procedimento pr;
52
• keys(v) - retorna o conjunto de índices de um vetor dinâmico v;
• ids(s) - retorna o conjunto de identificadores associados às mensagens do conjunto s.
São definidas os seguintes procedimentos, auxiliares às tarefas:
• AddInternalSusp(q, m) (linhas 5-7 do Algoritmo 1): adiciona uma suspeita interna ao
processo q em relação à mensagem m;
• AddExternalSusp(q, idm, ps) (linhas 9-13 do Algoritmo 1): adiciona uma suspeita externa
ao processo q proveniente do processo ps em relação à mensagem com identificado idm.
Adicionalmente, caso existam f + 1 ou mais suspeitas externas sobre q em relação a
message(idm), gera-se uma suspeita interna equivalente, caso ainda não exista;
• AddMistake(q, m) (linhas 15-22 do Algoritmo 1): adiciona um equívoco sobre a suspeita
de q não ter enviado m, retirando todas as suspeitas internas e externas associadas e, caso
q não tenha outras suspeitas nem tenha apresentado comportamento bizantino, remove-o
da saída do detector de falhas;
• AddByzantine(q, m) (linhas 24-26 do Algoritmo 1): adiciona-se q permanentemente à
lista de processos maliciosos (e, conseqüentemente, à saída do FD), juntamente com a
mensagem m associada à falha bizantina, servindo como prova da falha;
• ValidateReceived(m, q) (Algoritmo 1, linhas 28-33): verifica-se a validade (boa forma-
ção e justificação) de uma mensagem m recebida de q, retirando quaisquer suspeitas as-
sociadas ao par (q, m), caso m seja válida, e gerando uma suspeita de comportamento
comissivo, caso contrário;
• Verify(m, procedure) (linhas 1-6 do Algoritmo 3, utilizado pela tarefa T4): verifica se a
mensagem/informação m está devidamente assinada. Caso verdadeiro, avalia e executa
a chamada de procedimento procedure; caso contrário, marca o processo que enviou a
mensagem SUSPICION atual como malicioso.
O funcionamento de cada tarefa é descrito a seguir:
1. Geração de novas suspeitas (linhas 1-11 do Algoritmo 2). Quando o algoritmo A requer
que os processos troquem entre si uma mensagem m (linha 2), cada processo pi aguarda
receber m de pelo menos d− f processos, cujos identificadores são armazenados no con-
junto rec_ f romi (linhas 3-4). Para os demais processos conhecidos por pi, é adicionada
53
uma suspeita interna de falha por omissão (linhas 5-7). Cada mensagem é então verificada
quanto à sua formação e certificação (linhas 8-11 do Algoritmo 2 e 28-33 do Algoritmo
1). Mensagens incorretas levam a suspeitas de falhas por comissão (linhas 29-30 do
Algoritmo 1), atualizando os conjuntos byzantinei e a saída do detector de falhas; mensa-
gens corretas levam à geração de equívocos de possíveis suspeitas de falhas por omissão
(linhas 31-32 do Algoritmo 1).
2. Recepção de mensagens de processos lentos (linhas 13-16 do Algoritmo 2). Uma vez
que as mensagens enviadas por um processo lento podem ser recebidas após a geração
das suspeitas pelos seus vizinhos, é necessário que estes identifiquem tais eventos sepa-
radamente, o que é feito por esta tarefa. As mensagens são tratadas de forma similar à
tarefa T1.
3. Divulgação do novo estado de suspeitas e equívocos (linhas 18-24 do Algoritmo 2).
Esta tarefa é executada periodicamente para enviar aos vizinhos de um processo pi (linha
21) a visão de pi quanto às suspeitas (internas e externas), equívocos e provas de falha
por comissão. A divulgação do estado só é realizada quando este é modificado, o que
é verificado através da variável changed_state (linhas 20 e 23), que é atualizada a cada
modificação no estado do processo (linhas 7, 10, 22 e 26 do Algoritmo 1).
4. Atualização do estado interno (linhas 8-44 do Algoritmo 3). Ao receber uma mensagem
SUSPICION de um vizinho p j (linha 9), um processo pi atualiza seu estado interno com
novas informações. Provas de comportamento comissivo e informações de equívoco são
tratadas de forma similar às mensagens recebidas diretamente do remetente (linhas 16 e
33-40). Suspeitas internas e externas a p j são adicionadas ao conjunto de suspeitas exter-
nas de pi (linhas 21-31), possivelmente gerando novas suspeitas internas (linhas 11-13 do
Algoritmo 1). Adicionalmente, suspeita-se de falha por comissão do processo p j (linhas
42-44) caso a mensagem SUSPICION m esteja mal-formada ou não justificada (linhas 12-
13), caso uma mensagem correta esteja no conjunto byzantine j (linhas 17-19) ou uma
mensagem incorreta esteja no conjunto mistake j (linhas 36-38), ou ainda caso provas de
comportamento malicioso (linha 16), suspeitas reencaminhadas (linhas 24) ou provas de
equívocos (linha 35) contidas em m não estejam devidamente assinadas (tal verificação
é feita no procedimento Verify, linhas 1-6 do Algoritmo 3). A informação válida, no
entanto, é aproveitada. Neste caso, não se configura uma falha não-diagnosticável, pois
processos corretos devem descartar mensagens não assinadas e conseqüentemente não
reencaminhá-las.
54
5.6 ESBOÇO DE PROVA DE CORRETUDE
A corretude do algoritmo é definida em função das propriedades de completude forte bi-
zantina e precisão fraca após um tempo da classe ♦S (Byz,A ) de detectores de falhas. Dessa
forma, os argumentos são exibidos para cada propriedade separadamente:
1. Completude forte bizantina. Se um processo pi falhar por omissão, não enviando uma
mensagem m requerida pelo algoritmo A , os demais processos em rangei suspeitarão de
pi com base no mecanismo de espera de d− f mensagens descrito na Seção 5.3 (linhas
2-7 do Algoritmo 2). Devido às propriedades de f -cobertura bizantina e ByzMP , pelo
menos f + 1 processos corretos suspeitarão corretamente de pi, armazenando a suspeita
em seus conjuntos internal_state e atualizando a variável changed_state (linhas 5-7 do
Algoritmo 1), de forma que as suspeitas serão divulgadas aos seus vizinhos em uma
mensagem SUSPICION na próxima execução da tarefa T3 (linhas 18-24 do Algoritmo 2).
A propagação das suspeitas na rede é garantida pela tarefa T4. Seja p j um vizinho correto
de um processo falho pi. Ao receber uma mensagem SUSPICION de p j, um processo cor-
reto pk armazena as suspeitas de p j como suspeitas externas (linhas 28-32 do Algoritmo
3), no caso de falhas por omissão. Como as suspeitas externas são re-encaminhadas pelos
processos que as recebem (linhas 21 do Algoritmo 2 e 21-27 do Algoritmo 3), devido à
propriedade de f -cobertura bizantina, por indução, em algum momento futuro pk rece-
berá mais f suspeitas externas associadas ao par (pi, m), adotando assim essa suspeita
(linhas 11-13 do Algoritmo 1). Por indução, verifica-se que todos os processos corretos
da rede acabarão por suspeitar de pi não ter enviado m.
Da mesma forma, se pi cometer uma falha por comissão, a mesma será identificada por
seus vizinhos na chamada ao procedimento ValidateReceived da linha 10 do Algoritmo
2, nas linhas 12-13, 17-19 e 36-38 do Algoritmo 3 ou nas chamadas ao procedimento
Verify (linhas 1-6 do Algoritmo 3) nas linhas 16, 24 e 35 do Algoritmo 3. Por argumento
semelhante ao exibido para falha por omissão, a mensagem associada m é armazenada no
conjunto byzantine e transmitida aos vizinhos dos processos em rangei em uma mensa-
gem SUSPICION. Ao receber a mensagem SUSPICION de um processo p j vizinho a pi,
um processo pk vizinho a p j analisará a mensagem m (linhas 15-20 do Algoritmo 3) e,
uma vez que as mensagens são autenticadas, poderá constatar a falha do processo pi. Por
indução, em algum momento futuro todo processo correto na rede recebe a evidência da
falha.
55
2. Precisão fraca após um tempo. Seja pi um processo que nunca falhe e que atenda à pro-
priedade ByzRP . Como as mensagens são autenticadas e pi é correto, nenhum processo
malicioso poderá divulgar que pi cometeu uma falha por comissão. Pela propriedade
ByzRP , existirá um instante t após o qual as mensagens de pi requeridas por A serão
sempre recebidas pelos processos em rangei na linha 3 do Algoritmo 2. Desta forma, os
processos corretos em rangei nunca mais suspeitarão de pi. Haverá ainda um instante
u > t após o qual toda suspeita sobre pi anterior a t será revogada pelos vizinhos de pi
(linhas 8-11 e 13-16 do Algoritmo 2 e 15-22 do Algoritmo 1) e divulgada por toda a rede,
por argumento semelhante ao feito quanto à divulgação das suspeitas e pela atualização
feita nas linhas 33-40 do Algoritmo 3, de forma que nenhum processo correto suspeitará
de pi após u. Se um ou mais processos maliciosos levantarem uma suspeita sobre pi após
t, como existem no máximo f processos faltosos no sistema, não seria possível conven-
cer os processos corretos de adotarem tal suspeita, visto que seriam necessárias suspeitas
provenientes de f +1 processos distintos.
56
Algoritmo 1 Detector Assíncrono de Falhas Bizantinas em Sistemas Dinâmicos1: init:2: out puti← knowni← /0; changed_state← true3: external_suspi← [][]; internal_suspi← mistakei← []; byzantinei← /04:5: procedure AddInternalSusp(q, m):6: internal_suspi[q]← internal_suspi[q]∪m.id7: out puti← out puti∪q; changed_state← true8:9: procedure AddExternalSusp(q, idm, ps):
10: external_suspi[q][idm]← external_suspi[q][idm]∪p j; changed_state← true11: if |external_suspi[q][idm]| ≥ f +1 and idm /∈ internal_suspi[q] then12: AddInternalSusp(q, message(idm))13: end if14:15: procedure AddMistake(q, m):16: mistakei[q]← mistakei[q]∪m17: internal_suspi[q]← internal_suspi[q]\m.id18: external_suspi[q][m.id]← /019: if internal_suspi[q] = [] and @〈q,−〉 ∈ byzantinei then20: out puti← out puti \q21: end if22: changed_state← true23:24: procedure AddByzantine(q, m):25: out puti← out puti∪q; byzantinei← byzantinei∪〈q,m〉26: changed_state← true27:28: procedure ValidateReceived(m, q):29: if m não está devidamente formada or m não está devidamente justificada then30: AddByzantine(q, m)31: else if m.id ∈ internal_suspi[q] then32: AddMistake(q, m)33: end if
57
Algoritmo 2 Detector Assíncrono de Falhas Bizantinas em Sistemas Dinâmicos (continuação)1: Task T1: /* geração de novas suspeitas */2: when pi requer uma mensagem m do3: wait until receber m devidamente autenticada pela primeira vez de pelo menos (d− f )
processos distintos4: rec_ f romi←p j | pi recebeu uma mensagem de p j na linha 35: for all p j ∈ (knowni \ rec_ f romi) do6: AddInternalSusp(p j, m)7: end for8: for all m j recebida na linha 3 from p j do9: knowni← knowni∪p j
10: ValidateReceived(m j, p j)11: end for12:13: Task T2: /* recepção de mensagens de processos lentos */14: upon receipt of m devidamente autenticada from p j do15: knowni← knowni∪p j16: ValidateReceived(m, p j)17:18: Task T3: /* difusão do novo estado das suspeitas e equívocos */19: loop20: if changed_state then21: broadcast 〈SUSPICION, byzantinei, internal_suspi, external_suspi, mistakei〉22: end if23: changed_state← false24: end loop
58
Algoritmo 3 Detector Assíncrono de Falhas Bizantinas em Sistemas Dinâmicos (continuação)1: procedure Verify(m, procedure):2: if m está devidamente autenticada then3: eval(procedure)4: else5: byzantine← true6: end if7:8: Task T4: /* atualização do estado interno do processo */9: upon reception of m = 〈SUSPICION, byzantine j, internal_susp j, external_suspi,
mistake j〉 devidamente autenticada from p j do10: byzantine← false11: knowni← knowni∪p j12: if m não está devidamente formada then13: byzantine← true14: else15: for all 〈px,mx〉 ∈ byzantine j | @〈px,−〉 ∈ byzantinei do16: Verify(mx, ValidateReceived(mx, px))17: if mx está devidamente formada and mx está devidamente justificada then18: byzantine← true19: end if20: end for21: for all px ∈ keys(external_susp j) | @〈px,−〉 ∈ byzantinei do22: for all idmx ∈ keys(external_susp j[px]) | idmx /∈ internal_suspi[px]∪
ids(mistakei[px]) do23: for all py ∈ external_susp j[px][idmx] do24: Verify(mx, AddExternalSusp(px, idmx, py))25: end for26: end for27: end for28: for all px ∈ keys(internal_susp j) | 〈px,−〉 /∈ byzantinei do29: for all idmx ∈ internal_susp j[px] | idmx /∈ internal_suspi[px]∪ ids(mistakei[px]) do30: AddExternalSusp(px, idmx, p j)31: end for32: end for33: for all px ∈ keys(mistake j) | 〈px,−〉 /∈ byzantinei do34: for all mx ∈ mistake j[px] | mx /∈ mistakei[px] do35: Verify(mx, ValidateReceived(mx, px))36: if mx não está devidamente formada or mx não está devidamente justificada then37: byzantine← true38: end if39: end for40: end for41: end if42: if byzantine then43: AddByzantine(p j, m)44: end if
59
6 CONCLUSÃO
Este trabalho apresenta um detector de falhas bizantinas para sistemas distribuídos com
participantes desconhecidos. O detector é assíncrono, isto é, não se utiliza de temporizadores
(timeouts) para a detecção das falhas de progresso. Verifica-se assim a viabilidade da detecção
de falhas bizantinas em sistemas dinâmicos. No entanto, para que a detecção seja realizada de
forma assíncrona, acredita-se ser necessário que o padrão de comunicação do algoritmo que
utiliza o detector de falhas seja do tipo n→ n, isto é, que a cada passo todos os processos
troquem mensagens entre si.
Verifica-se ainda que a suposição de comunicação apenas por difusão (broadcast) e de ca-
nais confiáveis simplifica o tratamento de falhas bizantinas, uma vez que os processos vizinhos
de um remetente têm uma visão uniforme das mensagens por ele enviadas. Especificamente,
não é necessário tratar a ocorrência de mensagens mutantes, isto é, quando um mesmo processo
envia a mesma mensagem com conteúdos diferentes para diferentes processos.
Foi apresentada também uma revisão teórica dos modelos de sistemas distribuídos presentes
na literatura, em especial do modelo de falhas bizantinas e dos sistemas distribuídos dinâmicos;
do conceito de detectores de falhas e do problema do consenso, como motivação para o uso
dessa abstração.
6.1 DIFICULDADES ENCONTRADAS
Além de ser uma área de pesquisa muito teórica, a quantidade de considerações necessárias
para o desenvolvimento de algoritmos distribuídos torna este tipo de trabalho muitas vezes
exaustivo, o que, muitas vezes, não fica claro devido à simplicidade dos protocolos resultantes.
Demanda-se um tempo relativamente grande de leitura para que se tenha uma visão clara e
abrangente do domínio dos problemas abordados (o que pode ser verificado pela quantidade de
referências citadas).
O modelo de falhas bizantinas, em especial, devido às inúmeras possibilidades de compor-
tamento malicioso que podem ser apresentadas, tem recebido pouca atenção da comunidade
60
de computação distribuída, se for levada em consideração a demanda crescente por sistemas
seguros. A interação entre a pesquisa em tolerância a falhas e segurança da informação ainda
é pequena. Foi difícil, por exemplo, encontrar na literatura categorizações bem-definidas de
falhas bizantinas, exceto por trabalhos como (BALDONI et al., 1999; KIHLSTROM; MOSER;
MELLIAR-SMITH, 2003).
6.2 TRABALHOS FUTUROS
Objetivam-se como trabalhos futuros:
• Estender o protocolo para prover tolerância à mobilidade dos nós;
• Provar formalmente a corretude do algoritmo proposto;
• Analisar a complexidade da troca de mensagens no algoritmo;
• Implementação do protocolo, com o objetivo de avaliar seu desempenho e viabilidade
prática;
• Provar ou contra-exemplificar a impossibilidade de realização de detecção de falhas de
forma assíncrona em sistemas dinâmicos sujeitos a falhas bizantinas que requeiram co-
municação do tipo 1→ n;
• Divulgação do trabalho em conferências e/ou periódicos, com vistas a verificar sua acei-
tação pela comunidade científica.
61
REFERÊNCIAS BIBLIOGRÁFICAS
AGUILERA, M. K. A Pleasant Stroll through the Land of Infinitely Many Creatures. ACMSIGACT News, v. 35, n. 2, p. 36–59, June 2004.
AGUILERA, M. K. et al. Stable Leader Election. In: DISC ’01: Proceedings of the 15thInternational Conference on Distributed Computing. London, UK: Springer-Verlag, 2001. p.108–122. ISBN 3-540-42605-1.
AGUILERA, M. K. et al. Consensus with Byzantine Failures and Little System Synchrony.In: International Conference on Dependable Systems and Networks 2006 (DSN’06). LosAlamitos, CA, USA: IEEE Computer Society, 2006. p. 147–155.
ALCHIERI, E. A. P. et al. Consenso Bizantino entre Participantes Desconhecidos. In: WTF2008: IX Workshop de Teste e Tolerância a Falhas. Rio de Janeiro, Brazil: Sociedade Brasileirade Computação, 2008.
BALDONI, R.; HÉLARY, J.-M.; PIERGIOVANNI, S. T. A Component-Based Methodologyto Design Arbitrary Failure Detectors for Distributed Protocols. In: Proceedings of the 10thIEEE International Symposium on Object and Component-Oriented Real-Time DistributedComputing (ISORC’07). Washington, DC, USA: IEEE Computer Society, 2007. p. 51–61.
BALDONI, R. et al. Consensus in Byzantine Asynchronous Systems. Institut National deRecherche en Informatique et en Automatique, Rennes, France, 1999.
BONDY, J. A.; MURTY, U. S. R. Graph Theory with Applications. New York, NY:MacMillan/Elsevier, 1976. ISBN 0-444-19451-7.
CAVIN, D.; SASSON, Y.; SCHIPER, A. Consensus with Unknown Participants orFundamental Self-Organization. In: Ad-Hoc, Mobile, and Wireless Networks. [S.l.]: SpringerBerlin / Heidelberg, 2004, (Lecture Notes in Computer Science, v. 3158/2004). p. 135–148.ISBN 978-3-540-22543-0.
CAVIN, D.; SASSON, Y.; SCHIPER, A. Reaching Agreement with Unknown Participants inMobile Self-Organized Networks in Spite of Process Crashes. Ecole Polytechnique Federale deLausanne, France, 2005.
CHANDRA, T. D.; HADZILACOS, V.; TOUEG, S. The weakest failure detector for solvingconsensus. J. ACM, ACM, New York, NY, USA, v. 43, n. 4, p. 685–722, 1996. ISSN0004-5411.
CHANDRA, T. D.; TOUEG, S. Unreliable failure detectors for reliable distributed systems. J.ACM, ACM, New York, NY, USA, v. 43, n. 2, p. 225–267, 1996. ISSN 0004-5411.
62
CORREIA, M.; VERÍSSIMO, P.; NEVES, N. F. Byzantine Consensus in AsynchronousMessage-Passing Systems: a Survey. In: Resilience-building Technologies: State ofKnowledge. [S.l.]: RESIST Network of Excellence, 2006, (Deliverable D12, Part Algo). cap. 1.
COULOURIS, G.; DOLLIMORE, J.; KINDBERG, T. Sistemas distribuídos: conceito eprojeto. 4a. ed. Porto Alegre: Bookman, 2007.
DOLEV, D.; DWORK, C.; STOCKMEYER, L. On the minimal synchronism needed fordistributed consensus. J. ACM, ACM, New York, NY, USA, v. 34, n. 1, p. 77–97, 1987. ISSN0004-5411.
DOUCEUR, J. R. The sybil attack. In: IPTPS ’01: Revised Papers from the First InternationalWorkshop on Peer-to-Peer Systems. London, UK: Springer-Verlag, 2002. p. 251–260. ISBN3-540-44179-4.
DOUDOU, A.; SCHIPER, A. Muteness detectors for consensus with byzantine processes.In: PODC ’98: Proceedings of the seventeenth annual ACM symposium on Principles ofdistributed computing. New York, NY, USA: ACM, 1998. p. 315. ISBN 0-89791-977-7.
DWORK, C.; LYNCH, N.; STOCKMEYER, L. Consensus in the presence of partial synchrony.J. ACM, ACM, New York, NY, USA, v. 35, n. 2, p. 288–323, 1988. ISSN 0004-5411.
FERNÁNDEZ, A.; JIMÉNEZ, E.; ARÉVALO, S. Minimal system conditions to implementunreliable failure detectors. In: 12th Pacific Rim International Symposium on DependableComputing (PRDC’06). Los Alamitos, CA, USA: IEEE Computer Society, 2006. p. 63–72.ISBN 0-7695-2724-8.
FERNÁNDEZ, A.; JIMÉNEZ, E.; RAYNAL, M. Eventual Leader Election with WeakAssumptions on Initial Knowledge, Communication Reliability, and Synchrony. In:Proceedings of the 2006 International Conference on Dependable Systems and Networks(DSN’06). Los Alamitos, CA, USA: IEEE Computer Society, 2006. p. 166–178. ISBN0-7695-2607-1.
FISCHER, M. J.; LYNCH, N. A.; PATERSON, M. S. Impossibility of distributed consensuswith one faulty process. J. ACM, ACM, New York, NY, USA, v. 32, n. 2, p. 374–382, 1985.ISSN 0004-5411.
FRIEDMAN, R.; TCHARNY, G. Evaluating failure detection in mobile ad-hoc networks. Int.Journal of Wireless and Mobile Computing, v. 1, n. 8, 2005.
GREVE, F.; TIXEUIL, S. Knowledge Connectivity vs. Synchrony Requirements for Fault-Tolerant Agreement in Unknown Networks. In: DSN ’07: Proceedings of the 37th AnnualIEEE/IFIP International Conference on Dependable Systems and Networks. Washington, DC,USA: IEEE Computer Society, 2007. p. 82–91. ISBN 0-7695-2855-4.
GREVE, F. G. P. Protocolos Fundamentais para o Desenvolvimento de Aplicações Robustas.In: Minicursos SBRC 2005: Brazilian Symposium on Computer Networks. Fortaleza, CE,Brazil: Sociedade Brasileira de Computação, 2005. p. 330–398.
GUERRAOUI, R.; RAYNAL, M. The Information Structure of Indulgent Consensus. IEEETrans. Comput., IEEE Computer Society, Washington, DC, USA, v. 53, n. 4, p. 453–466, 2004.ISSN 0018-9340.
63
GUPTA, I.; CHANDRA, T. D.; GOLDSZMIDT, G. S. On scalable and efficient distributedfailure detectors. In: Proc. of the twentieth Annual ACM Symposium on Principles ofDistributed Computing. New York, NY, USA: ACM Press, 2001. p. 170–179.
HADZILACOS, V.; TOUEG, S. Fault-Tolerant Broadcasts and Related Problems. In:Distributed systems (2nd Ed.). New York, NY, USA: ACM Press/Addison-Wesley PublishingCo., 1993. p. 97–145. ISBN 0-201-62427-3.
HURFIN, M. et al. A General Framework to Solve Agreement Problems. In: SRDS ’99:Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems. Washington, DC,USA: IEEE Computer Society, 1999. p. 56. ISBN 0-7695-0290-3.
JIMÉNEZ, E.; ARÉVALO, S.; FERNÁNDEZ, A. Implementing unreliable failure detectorswith unknown membership. Inf. Process. Lett., Elsevier North-Holland, Inc., Amsterdam, TheNetherlands, The Netherlands, v. 100, n. 2, p. 60–63, 2006. ISSN 0020-0190.
KIHLSTROM, K. P.; MOSER, L. E.; MELLIAR-SMITH, P. M. Byzantine Fault Detectors forSolving Consensus. The Computer Journal, British Computer Society, v. 46, n. 1, p. 16–35,January 2003.
LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun.ACM, ACM, New York, NY, USA, v. 21, n. 7, p. 558–565, 1978. ISSN 0001-0782.
LAMPORT, L. The part-time parliament. ACM Trans. Comput. Syst., ACM, New York, NY,USA, v. 16, n. 2, p. 133–169, 1998. ISSN 0734-2071.
LAMPORT, L.; SHOSTAK, R.; PEASE, M. The byzantine generals problem. ACM Trans.Program. Lang. Syst., ACM, New York, NY, USA, v. 4, n. 3, p. 382–401, 1982. ISSN0164-0925.
LARREA, M.; FERNÁNDEZ, A.; ARÉVALO, S. Optimal implementation of the weakestfailure detector for solving consensus. In: SRDS ’00: Proceedings of the 19th IEEE Symposiumon Reliable Distributed Systems (SRDS’00). Washington, DC, USA: IEEE Computer Society,2000. p. 52–59. ISBN 0-7695-0543-0.
MALKHI, D.; REITER, M. Unreliable intrusion detection in distributed computations. In:Proc. 10th Computer Security Foundations Workshop. Rockport, MA: IEEE Computer SocietyPress, Los Alamitos, CA, 1997. p. 116–124.
MARTIN, J.-P.; ALVISI, L. Fast Byzantine Consensus. IEEE Trans. Dependable Secur.Comput., IEEE Computer Society Press, Los Alamitos, CA, USA, v. 3, n. 3, p. 202–215, 2006.ISSN 1545-5971.
MOSTEFAOUI, A.; MOURGAYA, E.; RAYNAL, M. Asynchronous Implementation ofFailure Detectors. In: Proceedings of the 2003 International Conference on DependableSystems and Networks (DSN’03). Los Alamitos, CA, USA: IEEE Computer Society, 2003.p. 351. ISBN 0-7695-1952-0.
MOSTEFAOUI, A.; RAYNAL, M. Leader-based consensus. Parallel Processing Letters,World Scientific Publishing Company, v. 11, n. 1, p. 95–107, March 2001.
64
MOSTEFAOUI, A.; RAYNAL, M.; TRAVERS, C. Crash-resilient Time-free EventualLeadership. In: Proceedings of the 23rd IEEE International Symposium on ReliableDistributed Systems (SRDS’04). Los Alamitos, CA, USA: IEEE Computer Society, 2004. p.208–217. ISSN 1060-9857.
MOSTEFAOUI, A. et al. From Static Distributed Systems to Dynamic Systems. In:Proceedings of the 2005 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05).Los Alamitos, CA, USA: IEEE Computer Society, 2005. p. 109–118. ISBN 0-7695-2463-X.
MOSTEFAOUI, A. et al. From Failure Detectors with Limited Scope Accuracy to System-wideLeadership. In: AINA ’06: Proceedings of the 20th International Conference on AdvancedInformation Networking and Applications - Volume 1 (AINA’06). Washington, DC, USA: IEEEComputer Society, 2006. p. 81–86. ISBN 0-7695-2466-4-01.
PEASE, M.; SHOSTAK, R.; LAMPORT, L. Reaching Agreement in the Presence of Faults. J.ACM, ACM, New York, NY, USA, v. 27, n. 2, p. 228–234, 1980. ISSN 0004-5411.
RAYNAL, M. Eventual Leader Service in Unreliable Asynchronous Systems: Why? How?Institut National de Recherche en Informatique et Systèmes Aléatoires, Rennes Cedex, France,2007.
RIVEST, R. L.; SHAMIR, A.; ADLEMAN, L. A method for obtaining digital signatures andpublic-key cryptosystems. Commun. ACM, v. 21, p. 120–126, 1978.
SCHNEIDER, F. B. What good are models and what models are good? In: Distributed systems(2nd Ed.). New York, NY, USA: ACM Press/Addison-Wesley Publishing Co., 1993. p. 17–26.ISBN 0-201-62427-3.
SCHNEIDER, M. Self-stabilization. ACM Computing Surveys, ACM, v. 25, n. 1, p. 45–67,1993.
SENS, P. et al. Um Detector de Falhas Assíncrono para Redes Móveis e Auto-Organizáveis.In: SBRC 2008: Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos. Riode Janeiro, RJ, Brazil: [s.n.], 2008.
VERISSIMO, P.; RODRIGUES, L. Distributed Systems for System Architects. Norwell, MA,USA: Kluwer Academic Publishers, 2001. ISBN 0792372662.
