UNIVERSIDADE TECNOLOGICA FEDERAL DO PARANA
Programa de Pos-Graduacao em Engenharia Eletrica e Informatica Industrial
TESE
apresentada a Universidade Tecnologica Federal do Parana
para a obtencao do grau de
DOUTOR EM CIENCIAS
por
LUIS CARLOS ERPEN DE BONA
HYPERBONE: UMA REDE OVERLAY BASEADA EM HIPERCUBO
VIRTUAL PARA COMPUTACAO DISTRIBUIDA NA INTERNET
Banca Examinadora:
Orientador:
Prof. Dr. ELIAS PROCOPIO DUARTE JR. DEP. INFORMATICA, UFPR
Co-orientador:
Profa. Dra. KEIKO VERONICA ONO FONSECA CPGEI, UTFPR
Examinadores:
Prof. Dr. BRUNO SCHULZE LNCC, MCT
Prof. Dr. SERGIO SCHEER CESEC, UFPR
Prof. Dr. CARLOS ALBERTO MAZIERO PPGIA, PUCPR
Prof. Dr. LUIS ALLAN KUNZLE DEP. INFORMATICA, UFPR
Curitiba, Julho de 2006.
Luis Carlos Erpen De Bona
HyperBone: Uma Rede Overlay
Baseada em Hipercubo Virtual para
Computacao Distribuıda na Internet
Tese submetida ao Programa de Pos-Graduacao em
Engenharia Eletrica e Informatica Industrial da Uni-
versidade Tecnologica Federal do Parana como requi-
sito parcial para a obtencao do grau de Doutor em
Ciencias.
Orientador: Prof. Dr. Elias P. Duarte Jr.
Co-orientadora: Profa. Dra. Keiko V. O. Fonseca.
CURITIBA
2006
Dedico esta tese,
A memoria de meu pai, Luiz De Bona Neto.
Agradecimentos
Ao escrever estes agradecimentos, busquei lembrar de todos que de alguma maneira
estiveram presentes e foram decisivos para que esta tese existisse. Meu primeiro agrade-
cimento e para minha famılia, em especial meus pais, Adelia e Luiz (in memoriam), e
meu irmao Marco, que desde sempre nao mediram esforcos para oferecer todas condicoes
necessarias para que eu realizasse meus estudos.
Remetendo ao meu tempo de graduacao, poderia agradecer a varios professores que
eu admiro e foram importantes em minha formacao. Mas sei que estes entenderao meu
agradecimento: Prof. Alexandre Direne, meus sinceros e grandes agradecimentos por tudo.
No rumo da opcao pela vida academica, sem duvida, tenho muito a agradecer ao Prof.
Elias P. Duarte Jr., orientador deste trabalho e de muitos outros desde os tempos da ini-
ciacao cientıfica. Obrigado pelos ensinamentos, pela paciencia e pela ajuda em todos estes
anos. Aproveitando o tema da orientacao deste trabalho, agradecimentos a Profa. Keiko
O. Fonseca, que sempre ofereceu injecoes de animo e ajudou em tudo que foi necessario
para completar esta tese.
Na reta final, nao posso deixar de agradecer as pessoas presentes durante o perıodo
do sandwich em Barcelona: Joan Climent, Gema Albiach, Sandra Sandri e meninas, Roy
Verholen, Carlos Bonetti e Fabio Fonseca. Tios, salut i forca al canut. Na Universitat
Politecnica de Catalunya (UPC), agradeco fortemente ao Prof. Leandro Navarro e seu
grupo de pesquisa, que proporcionou recursos e ideias importantes para consolidar esta
tese, moltes gracies per tot.
Finalmente, meus grandes amigos, Marcos Castilho, Marcos Sunye, Lıgia Setenareski,
Fabiano Silva e Letıcia Peres, agradeco mais do que por esta tese: agradeco pela amizade,
pelas conversas e pela ajuda em todos momentos. So tenho a dizer, muito obrigado!
Though this be madness,
yet there is method in it
Hamlet, Act 2, Scene 2
Sumario
Lista de Figuras v
Lista de Tabelas vii
Resumo viii
Abstract ix
1 Introducao 1
2 Sistemas Distribuıdos de Larga Escala na Internet 5
2.1 Grades Computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Primeira Geracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Segunda Geracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Terceira Geracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Programacao Paralela e Distribuıda com MPI . . . . . . . . . . . . . . . . 18
2.3 Redes Overlay Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Diagnostico Distribuıdo 31
3.1 O Modelo PMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 O Algoritmo Adaptive-DSD . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 O Algoritmo Hi-ADSD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Sumario iii
3.4 O Algoritmo Hi-ADSD with Detours . . . . . . . . . . . . . . . . . . . . . 37
3.5 O Algoritmo Hi-ADSD with Timestamps . . . . . . . . . . . . . . . . . . . 41
3.5.1 Diagnostico Dinamico de Eventos . . . . . . . . . . . . . . . . . . . 42
3.5.2 Especificacao do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . 43
4 Diagnostico Distribuıdo Baseado no Algoritmo DiVHA 47
4.1 Modelo do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Especificacao do Algoritmo de Diagnostico Distribuıdo . . . . . . . . . . . 49
4.3 O Algoritmo DiVHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 Provas Formais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.5 Resultados de Simulacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.5.1 Numero de Testes Necessarios . . . . . . . . . . . . . . . . . . . . . 55
4.5.2 Latencia para Deteccao de Eventos . . . . . . . . . . . . . . . . . . 57
4.5.3 Comparacao com Outros Algoritmos . . . . . . . . . . . . . . . . . 59
5 HyperBone: Uma Rede Overlay Escalavel 62
5.1 Modelo do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Construindo e Mantendo o Hipercubo Virtual . . . . . . . . . . . . . . . . 64
5.2.1 Algoritmo de Roteamento no Hipercubo Virtual . . . . . . . . . . . 65
5.2.2 Parametros de Disponibilidade . . . . . . . . . . . . . . . . . . . . . 67
5.3 Exemplos de Execucao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 Implementacao e Resultados Experimentais . . . . . . . . . . . . . . . . . 71
5.4.1 Sistema de Monitoracao . . . . . . . . . . . . . . . . . . . . . . . . 71
5.4.2 Estrategia de Roteamento no HyperBone . . . . . . . . . . . . . . . 74
5.4.3 Executando Aplicacoes Paralelas no HyperBone . . . . . . . . . . . 76
6 Conclusao 81
Sumario iv
Referencias 84
Lista de Figuras
1 HyperBone formado por 8 nodos espalhados pela Internet. . . . . . . . . . 2
2 Sistema executando o algoritmo ADSD. . . . . . . . . . . . . . . . . . . . 34
3 Sistema de 8 nodos agrupados em clusters no algoritmo Hi-ADSD. . . . . 35
4 Clusters testados pelo nodo 0 executando o algoritmo Hi-ADSD. . . . . . 36
5 O grafo T (S) para um sistema com 8 nodos. . . . . . . . . . . . . . . . . 38
6 Sistema executando o algoritmo Hi-ADSD with Detours. . . . . . . . . . . 39
7 Especificacao do algoritmo Hi-ADSD with Detours. . . . . . . . . . . . . . 40
8 O grafo TFF0 para um sistema com 8 nodos. . . . . . . . . . . . . . . . . 44
9 Um exemplo de Ci,s,p: C0,3,2. . . . . . . . . . . . . . . . . . . . . . . . . . 44
10 Clusters testados pelo nodo 0. . . . . . . . . . . . . . . . . . . . . . . . . . 45
11 Diagnostico distribuıdo baseado no algoritmo DiVHA. . . . . . . . . . . . 50
12 Especificacao do algoritmo DiVHA. . . . . . . . . . . . . . . . . . . . . . . 51
13 Sistema de 8 nodos agrupados em clusters pelo algoritmo DiVHA. . . . . . 51
14 Aresta adicionada do nodo nk ∈ Ci,s para o nodo nl ∈ Cj,s. . . . . . . . . . 54
15 Numero de testes necessarios para um sistema com 64 nodos. . . . . . . . . 56
16 Numero de testes necessarios para um sistema com 128 nodos. . . . . . . . 57
17 Numero de testes necessarios para um sistema com 256 nodos. . . . . . . . 58
18 Latencia para sistemas com 512 nodos. . . . . . . . . . . . . . . . . . . . . 59
19 Latencia para sistemas com 32, 64, 128, 256, 512 e 1024 nodos. . . . . . . . 60
20 O algoritmo para criacao e manutencao do hipercubo virtual. . . . . . . . 65
21 Algoritmo de manutencao da tabela de rotas no HyperBone. . . . . . . . . 66
Lista de Figuras vi
22 Exemplo de roteamento para um sistema com 8 nodos no HyperBone. . . . 67
23 Algoritmo de atualizacao das informacoes sobre os estados de disponibili-
dade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
24 Exemplo de sistema com 16 nodos executando o HyperBone. . . . . . . . . 69
25 Representacao das iteracoes do algoritmo DiVHA. . . . . . . . . . . . . . . 70
26 Exemplo de sistema com 16 nodos apos falha do nodo 4. . . . . . . . . . . 70
27 Probabilidade acumulada para o tempo de permanencia nos estados working
e unresponsive. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
28 Probabilidade acumulada para o tempo de permanencia nos estados available
e unavailable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
29 Histograma da taxa de disponibilidade dos nodos. . . . . . . . . . . . . . . 75
30 Propagacao da informacao de um evento no nodo 4. . . . . . . . . . . . . 76
Lista de Tabelas
1 Ci,s para um sistema com 8 nodos. . . . . . . . . . . . . . . . . . . . . . . 36
2 Simulacoes de um sistema com 64 nodos executando os algoritmos Hi-ADSD
e Hi-ADSD com detours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Numero medio de testes necessarios para diagnosticar um sistema com 64
nodos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4 Latencia media para diagnosticar um evento em um sistema com 512 nodes. 61
5 Relacao de ganho da estrategia de roteamento do HyperBone. . . . . . . . 76
6 Resultados da execucao do MPIbench no HyperBone. . . . . . . . . . . . 77
7 Resultado da execucao de um buscador de senhas no HyperBone. . . . . . 77
8 Comparativo de vazao entre os dispositivos ch hyperbone e ch p4. . . . . . 79
9 Comparativo do tempo de execucao do MPI-PovRay entre os dispositivos
ch hyperbone e ch p4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Resumo
Este trabalho apresenta o HyperBone, uma rede overlay baseada em hipercubo virtual
que oferece servicos de monitoracao e roteamento, permitindo a execucao de aplicacoes dis-
tribuıdas na Internet. O hipercubo e uma estrutura escalavel por definicao, apresentando
caracterısticas topologicas importantes como: simetria, diametro logarıtmico e boas pro-
priedades para tolerancia a falhas. O hipercubo virtual e mantido pelo algoritmo DiVHA
(Distributed Virtual Hypercube Algorithm), que garante propriedades do hipercubo mesmo
quando o numero de nodos nao e potencia de dois. A especificacao do algoritmo DiVHA
e as provas formais de sua correcao sao apresentadas neste trabalho. Um algoritmo de di-
agnostico distribuıdo baseado no hipercubo virtual tambem e proposto. Sao apresentadas
as provas de correcao do algoritmo de diagnostico, bem como resultados experimentais obti-
dos por simulacao. No HyperBone e considerado um ambiente sujeito a situacoes dinamicas
de falhas, nas quais nodos falham e se recuperam continuamente, deixando o sistema para
depois serem reintegrados. Uma estrategia para classificar os nodos de acordo com sua
estabilidade e apresentada. Alem da monitoracao, o HyperBone oferece servicos de comu-
nicacao atraves do roteamento de mensagens. O algoritmo de roteamento proposto utiliza
as melhores rotas no hipercubo virtual. O HyperBone foi implementado no PlanetLab,
um ambiente constituıdo por nodos ao redor do mundo conectados pela Internet sujeitos a
altas carga de processamento e de trafego de rede. Os resultados experimentais mostram a
capacidade do HyperBone monitorar sistemas altamente instaveis como o PlanetLab, assim
como a capacidade de executar aplicacoes MPI paralelas usando o hipercubo virtual.
Abstract
This thesis presents HyperBone, an overlay network based on a virtual hypercube that
offers services such as monitoring and routing, allowing the execution of distributed ap-
plications across the Internet. Hypercubes are scalable by definition, presenting several
properties such as symmetry and logarithmic diameter, that are advantageous for distri-
buted and parallel applications. HyperBone nodes run the Distributed Virtual Hypercube
Algorithm (DiVHA) in order to keep hypercube properties even when the number of nodes
is not a power of two. The specification of the DiVHA algorithm as well as the formal
proofs of its correctness are presented. A distributed diagnosis algorithm based on the vir-
tual hypercube is also proposed, along with its experimental results accomplished through
simulation. The system is considered to be subject to a dynamic fault situation, in which
nodes may continuously fail and recover, vanishing from the system to possibly restart
further ahead in time. A strategy of node classification according to its stability is presen-
ted. Besides monitoring HyperBone also offers a routing service. The routing algorithm
proposed is capable of determining optimal routes in the virtual hypercube. HyperBone is
implemented in PlanetLab, an environment built up with nodes spread around the world
interconnected by the Internet, subjected to high processing and network loads. The expe-
rimental results suggest how capable HyperBone is of monitoring highly unstable systems,
such as PlanetLab, and of executing parallel MPI applications in the virtual hypercube.
1
1 Introducao
Diversos sistemas distribuıdos de larga escala tem surgido na Internet nos ultimos anos.
O desenvolvimento destes sistemas e consequencia da Internet ter permitido interconectar
um grande numero de recursos computacionais. Alem disso, protocolos e padroes vem
derrubando a barreira da heterogeneidade das tecnologias. A computacao em grade (FOS-
TER; KESSELMAN, 1997; OURGRID, 2005), ou grid computing, e as redes peer-to-peer (P2P)
(CLARK, 2001) sao exemplos de tecnologias que tem permitido acessar e utilizar esses re-
cursos, formando sistemas distribuıdos de grande porte e dinamicos, nos quais nodos nao
sao permanentes, se integrando e deixando continuamente o sistema, que esta sujeito a
falhas e recuperacoes tambem contınuas.
Uma abordagem promissora para construir esses sistemas distribuıdos de larga escala
na Internet sao as redes overlay (AMIR; DANILOV, 2003). Em princıpio as aplicacoes dis-
tribuıdas poderiam gerenciar seus recursos acessando diretamente a rede subjacente, mas
uma rede overlay pode oferecer servicos como manutencao da rede, seguranca e alta dispo-
nibilidade que dificilmente poderiam ser providos no nıvel de rede. Em redes P2P as redes
overlay tem sido utilizadas como forma de tornar o sistema escalavel (DOVAL; O’MAHONY,
2003), outras redes overlay destinam-se a melhorar os servicos oferecidos pelos protocolos
da Internet, como suportar QoS ou multicast (QBONE, 2005; ERIKSSON, 1994) ou ainda
oferecer formas de roteamento alternativas (ANDERSEN; BALAKRISHNAN; MORRIS, 2001).
Este trabalho apresenta o HyperBone (BONA; DUARTE Jr.; FONSECA, 2005; BONA et
al., 2006), uma rede overlay formada por nodos espalhados pela Internet interligados por
1 Introducao 2
enlaces virtuais, que sao arestas de um hipercubo virtual, implementadas como conexoes
TCP (Transmission Control Protocol) persistentes. Os nodos do HyperBone sao hosts da
Internet capazes de realizar tarefas de processamento. Os nodos realizam testes entre si e
trocam informacao sobre o resultado destes testes, implementando um sistema distribuıdo
de monitoracao. Se o numero de nodos e uma potencia de dois e todos nodos estao sem
falhas, a topologia do sistema e um hipercubo completo. A figura 1 mostra o HyperBone
sendo executado em 8 nodos, as linhas pontilhadas indicam os enlaces virtuais.
Figura 1: HyperBone formado por 8 nodos espalhados pela Internet.
A principal caracterıstica do sistema e a escalabilidade, o hipercubo e uma estrutura es-
calavel por definicao, que apresenta caracterısticas topologicas importantes como: simetria,
diametro logarıtmico e boas propriedades para tolerancia a falhas (TIEN; RAGHAVENDRA,
1993; KRULL; WU; MOLINA, 1992; SAAD; SCHULTZ, 1998). Deve ser destacado neste tra-
balho que as caracterısticas que dificultam a utilizacao dos hipercubos para arquiteturas
de maquinas paralelas nao estao presentes no hipercubo virtual: o numero de nodos nao
precisa ser potencia de dois e o custo de adicionar ligacoes, que sao virtuais, e baixo.
Mesmo quando o numero de nodos nao e potencia de dois ou alguns nodos nao estao
disponıveis, o HyperBone ainda e capaz de manter as propriedades logarıtmicas do hiper-
cubo. A topologia e mantida pelo HyperBone utilizando o algoritmo DiVHA (Distributed
1 Introducao 3
Virtual Hypercube Algorithm), tambem proposto neste trabalho. O DiVHA efetivamente
calcula os enlaces do hipercubo virtual, permitindo aos nodos se auto-organizarem man-
tendo caracterısticas do hipercubo como o diametro logarıtmico. O sistema e dinamico, ou
seja, os nodos podem falhar e se recuperar constantemente.
O algoritmo DiVHA esta relacionado com o diagnostico distribuıdo (MASSON; BLOUGH;
SULLIVAN, 1996). Os algoritmos de diagnostico definem estrategias de testes que permitem
que todos os nodos sem falha de um sistema determinem o estado de todos os outros
nodos do sistema. As assercoes sobre o sistema feitas pelos algoritmos de diagnostico sao
bastante diferentes das feitas no DiVHA, especialmente porque os algoritmos de diagnostico
consideram que os nodos sao capazes de determinar o estado de outros nodos com 100%
de precisao (PREPARATA; CHIEN, 1967), o que e uma assercao que nao pode ser cumprida
em sistemas assıncronos (FISCHER; LYNCH; PATERSON, 1985). Por outro lado, a forma
de organizar os testes e o fluxo de informacao e bastante semelhante. Tambem e proposto
neste trabalho um algoritmo de diagnostico distribuıdo baseado no DiVHA (BONA; DUARTE
Jr.; FONSECA, 2006). O algoritmo e formalmente especificado, sao apresentadas provas de
correcao e resultados experimentais obtidos atraves de simulacao.
As caracterısticas topologicas do hipercubo virtual permitem implementar um sistema
de monitoracao distribuıda onde os nodos sem falha podem determinar o estado de todos
outros nos do sistema em no maximo log2N rodadas de testes, requerendo no maximo
N ∗ (log2N)2 testes. De nosso conhecimento, nenhum outro algoritmo distribuıdo de mo-
nitoracao apresenta um numero tao baixo de mensagens. O HyperBone introduz ainda
uma estrategia que permite cada nodo manter uma lista dos nodos que estao apresentando
comportamento estavel e que podem ser utilizados para executar tarefas de processamento.
O HyperBone e capaz de rotear mensagens pelos enlaces do hipercubo virtual, ofe-
recendo um servico de comunicacao escalavel que permite a qualquer par de nodos se
comunicar diretamente usando rotas com distancia logarıtmica, sem a necessidade de esta-
belecer enlaces entre todos os nodos. Todo o trafego entre os nodos e tunelado pelos enlaces
1 Introducao 4
virtuais, facilitando a instalacao de nodos atras de firewalls restritivos. O roteamento no
hipercubo virtual permite ainda encontrar rotas alternativas aquelas usadas pelos nodos
quando se comunicam diretamente pela Internet. Uma estrategia de roteamento que per-
mite escolher as rotas com menor custo no hipercubo virtual tambem e apresentada neste
trabalho.
O HyperBone foi implementado no PlanetLab (PLANETLAB, 2005), um ambiente que
permite avaliar aplicacoes distribuıdas em escala global sob condicoes reais. Os resultados
experimentais mostram o funcionamento do sistema de monitoracao validando a estrategia
proposta para identificar nodos estaveis. Os experimentos tambem mostram a capacidade
de executar aplicacoes distribuıdas em escala mundial utilizando a rede overlay oferecida
pelo HyperBone, nestes experimentos foram executadas aplicacoes paralelas usando MPI
(Message Passing Interface) (MESSAGE PASSING INTERFACE FORUM, 1994). Uma imple-
mentacao alternativa do HyperBone (MELLO et al., 2006), que permite as aplicacoes MPI
acessarem diretamente o hipercubo virtual, tambem foi apresentada e avaliada.
O restante deste trabalho esta organizando da seguinte maneira. O capıtulo 2 apresenta
algumas das principais abordagens existentes atualmente para a organizacao de sistemas
distribuıdos de grande porte. O capıtulo 3 apresenta o diagnostico distribuıdo e os al-
goritmos de diagnostico relacionados com o DiVHA. No capıtulo 4, o algoritmo DiVHA
e especificado, e um novo algoritmo de diagnostico baseado do DiVHA e proposto, bem
como sao apresentadas provas formais de correcao e resultados experimentais obtidos por
simulacao. O HyperBone e apresentado e especificado no capıtulo 5, onde sao apresenta-
dos resultados da implementacao e execucao do HyperBone no PlanetLab. Finalmente, o
capıtulo 6 conclui este trabalho.
5
2 Sistemas Distribuıdos de Larga
Escala na Internet
A popularizacao das redes de computadores, em especial a Internet, permitiu interco-
nectar um grande numero de recursos computacionais. Os protocolos de rede difundidos
nas ultimas decadas derrubaram a barreira da heterogeneidade das diversas tecnologias de
redes. A disponibilidade destes recursos tem permitido o aparecimento de sistemas dis-
tribuıdos de larga escala, compostos por um grande numero de unidades espalhadas por
todo o planeta.
As redes overlay (AMIR; DANILOV, 2003) sao uma alternativa para implementar servicos
de rede distribuıdos. As redes overlay sao redes logicas construıdas sobre a rede fısica. Em
princıpio as aplicacoes distribuıdas poderiam gerenciar seus recursos acessando diretamente
a rede subjacente, mas uma rede overlay pode oferecer servicos como manutencao da rede,
seguranca e alta disponibilidade que dificilmente poderiam ser providos no nıvel de rede.
Este trabalho apresenta o HyperBone, uma rede overlay que permite a execucao de
aplicacoes distribuıdas na Internet. O HyperBone esta relacionado aos sistemas para com-
putacao em grades, uma das tecnologias que trata os problemas de agregar e coordenar
recursos na Internet, sendo apresentada na secao 2.1. Este trabalho apresenta exemplos de
execucoes de programas paralelos usando o HyperBone no PlanetLab. A secao 2.2 apre-
sentas os principais trabalho relacionados com a execucacao deste tipo de aplicacoes em
grades computacionais. As redes overlay P2P, que sao outra abordagem para o problema
de compartilhamento de recursos e execucao de tarefas, sao apresentadas na secao 2.3.
2.1 Grades Computacionais 6
2.1 Grades Computacionais
O objetivo principal de um ambiente de grades e compartilhar recursos computacionais
em grandes redes de computadores como a Internet. O termo grade computacional pode
ser empregado para muitos tipos de problemas de compartilhamento de recursos. Com
isto a definicao precisa do termo “grade” pode variar de acordo com fatores como o tipo,
uso e grau de heterogeneidade dos recursos envolvidos ou mesmo da arquitetura utilizada
pelo ambiente. Esta secao tem como objetivo apresentar diferentes conceitos e projetos
em grade computacionais. A subsecao 1 apresenta o que podem se considerar como os
primeiros esforcos e projetos de computacao em grade. A subsecao 2 apresenta a segunda
geracao de grades computacionais, um dos paradigmas mais estudados e desenvolvidas atu-
almente. Finalmente, a subsecao 3 apresenta um novo paradigma para o compartilhamento
de recursos, correspondente a terceira geracao de grade computacional.
2.1.1 Primeira Geracao
Os primeiros esforcos para a criacao de grades computacionais deram-se sob o nome de
metacomputacao por volta dos anos 1990 com a interligacao de sıtios de supercomputacao
com o objetivo de oferecer recursos computacionais para aplicacoes de alto desempenho. Os
projetos mais importantes sao de 1995 e foram o FAFNER (Factoring via Network-Enabled
Recursion) (NORTHEAST PARALLEL ARCHITECTURES CENTER, 2005) e o I-WAY (Infor-
mation Wide Area Year) (FOSTER et al., 1997), o primeiro relacionado com a interligacao
de estacoes de trabalho e o segundo com a unificacao de recursos de supercomputacao.
O FAFNER foi um projeto destinado a fatoracao de numeros muito grandes, um desafio
computacionalmente intensivo muito relevante para seguranca digital. Como este tipo de
processamento pode ser quebrado em pequenas partes, mesmo um computador bastante
modesto pode contribuir de forma util para o processamento. Outra caracterıstica desta
aplicacao e nao haver a necessidade de uma rede de alta velocidade. O FAFNER apresentou
2.1 Grades Computacionais 7
uma serie de limitacoes, como a grande necessidade de intervencao humana para recolher
os resultados e a incapacidade dos nodos se comunicarem entre si. Apesar disto, foi uma
iniciativa de sucesso, dando origem a sucessores como o SETI@home (SETI INSTITUTE,
2005).
O I-WAY foi um projeto direcionado a ligacao de supercomputadores. Era direcionado
a aplicacoes de alto desempenho, exigindo assim uso de redes de alta velocidade, ficando
limitado portanto a sıtios que possuıam esta estrutura. Uma das inovacoes do projeto foi
o desenvolvimento de um agenciador de recursos (resource broker), conceitualmente muito
similar aos agenciadores de recursos dos projetos de grade atuais.
Um experimento realizado com o I-WAY foi a tentativa de usar uma camada de comu-
nicacao chamada Nexus (FOSTER; KESSELMAN; TUECKE, 1996) para executar aplicacoes
paralelas. Apesar do grande esforco realizado nao foi possıvel obter um ambiente estavel
para execucao dessas aplicacoes. As causas provaveis foram a heterogeneidade dos sistemas
interligados por uma rede de baixa velocidade e uma limitacao da escala relacionada com
problema de exaustao de descritores de arquivos e sockets de rede abertos. Apesar deste
infortunio, o I-WAY e considerado uma experiencia de sucesso, influenciando o desenvolvi-
mento do projeto Globus (FOSTER; KESSELMAN, 1997; UNIVERSITY OF CHICAGO, 2005),
que e um dos padroes de grades mais aceitos atualmente, assim como o projeto Legion
(GRIMSHAW; WULF, 1997).
Apesar do FAFNER e do I-WAY serem considerados como as primeiras iniciativas em
grades computacionais, o termo grid propriamente dito so foi apresentado oficialmente com
a publicacao do livro The Grid: Blueprint for a New Computing Infrastructure (FOSTER;
KESSELMAN, 1998). O termo grid surge como uma analogia a rede eletrica (electric power
grid), que prove acesso a eletricidade de forma pervasiva e teve importancia dramatica
no desenvolvimento da sociedade. O grid denota uma infraestrutura para prover acesso
confiavel, consistente, pervasivo e barato para uma larga escala e variedade de recursos
computacionais.
2.1 Grades Computacionais 8
2.1.2 Segunda Geracao
As tecnologias de redes de alta velocidade e a adocao de padroes permitiram viabili-
zar as grades como uma infraestrutura distribuıda em escala global, suportando diversas
aplicacoes que requeiram computacao e dados em grande escala. Na segunda geracao fica
claro que a grade computacional deve ter como objetivo esconder a natureza heterogenea do
ambiente e prover aos usuarios e aplicacoes acesso aos recursos de uma maneira uniforme.
Os desafios a serem atacados sao a heterogeneidade, escalabilidade e adaptabilidade.
A heterogeneidade e um desafio porque um ambiente de grade envolve uma multiplici-
dade de recursos heterogeneos por natureza e sujeitos a diversos domınios administrativos.
Assim, e necessario se preocupar em como prover acesso uniforme aos diversos recursos sem
prejudicar as polıticas de administracao locais.
A escalabilidade tambem e um desafio porque um ambiente de grades pode envolver mi-
lhares ou ate milhoes de recursos em um unico ambiente, o que leva a potenciais problemas
de degradacao de desempenho e dificuldades para os sistemas de informacao e monitora-
mento. Alem disto a escala aumenta ainda mais o numero de organizacoes que podem
compor as grades, aumentando a heterogeneidade e a necessidade de tratar questoes de
autenticacao e confiabilidade.
Finalmente, a adaptabilidade tambem e um desafio, pois nao e esperado que um am-
biente de grade permaneca sem alteracoes por um longo perıodo. Os gerenciadores de
recursos e as aplicacoes devem ser capazes de comportar-se dinamicamente, extraindo o
maximo possıvel dos recursos disponıveis. Na questao de adaptabilidade tambem devem
ser considerados aspectos como a tolerancia a falhas.
Uma serie de caracterısticas sao esperadas de uma ambiente de grade:
Hierarquia administrativa: Espera-se que um ambiente de grades possa ser bastante
grande em termos de componentes (computadores e outros recursos de hardware ou
2.1 Grades Computacionais 9
software), nao e razoavel que cada componente do sistema tenha que interagir di-
retamente com todos os outros componentes. Assim, sao necessarios mecanismos e
estrategias para particionar o domınio e determinar o fluxo de informacao adminis-
trativa pela grade.
Servicos de comunicacao: As aplicacoes podem requerer diversas classes de servicos
de comunicacao, indo de comunicacao ponto-a-ponto confiavel ate multicast nao-
confiavel, ou ainda suporte aos protocolos usados para transferencia em grande vo-
lume (bulk), streaming, comunicacao em grupo e outros usados por paradigmas de
objetos distribuıdos. Alem disto, pode ser necessario atender alguns parametros de
qualidade de servicos (QoS - Quality of Service) . O ambiente de grade deve estar
preparado para atender ou pelo menos permitir estas diversas classes de servico de
comunicacao.
Servicos de informacao: No ambiente de grades pode estar disponıvel um grande con-
junto de recursos de caracterısticas distintas. Devido a dinamicidade do ambiente a
tendencia e que exista uma grande variacao neste conjunto com a entrada de novos re-
cursos e o desaparecimento de outros. Assim, e necessario um servico de informacao
que ofereca um servico de diretorio para prover informacoes sobre os recursos dis-
ponıveis e um mecanismos que permita aos domınios administrativos registrar in-
formacoes sobre os recursos disponıveis.
Servico de nomes: E necessario que a grade tenha um espaco de nomes uniforme que
permita nomear a grande variedade de recursos, como computadores, servicos ou da-
dos, que compoem o sistema. Em alguns sistemas o DNS (Domain Name Service)
pode ser suficiente, porem e comum que seja necessario utilizar esquemas mais com-
plexos como o LDAP (Lightweight Directory Access Protocol) (WAHL; KILLE; HOWES,
1997) .
Sistema de arquivos distribuıdos: As aplicacoes distribuıdas geralmente requerem acesso
2.1 Grades Computacionais 10
a arquivos que podem estar distribuıdos entre muitos servidores. Um sistema de ar-
quivos distribuıdos prove um espaco de nome global, suporte a uma diversidade de
protocolos da maneira mais transparente possıvel para as aplicacoes e ainda se preo-
cupa com as questoes de otimizacao e desempenho proprias do ambiente.
Seguranca e autorizacao: A seguranca e uma das questoes mais complexas e impor-
tantes. Os recursos envolvidos estao sujeitos a polıticas de administracao diversas
que precisam interagir para proporcionar os acessos necessarios de forma segura. As
questoes de confidencialidade, integridade, autenticacao e auditabilidade devem ser
sempre observadas. A seguranca deve se preocupar nao apenas em negar ou permitir
acesso, mas tambem em delimitar este acesso.
Monitoracao: A dinamicidade do ambiente de grade impoe que sempre existam compo-
nentes do sistema mudando de estado. Ainda podem ser implementados mecanismos
de tolerancia a falhas que precisam conhecer o estado do sistema. Desta forma, um
ambiente de grades necessita prover ferramentas que permitam monitorar seus com-
ponentes.
Gerenciamento de recursos: Alem de permitir o acesso aos recursos e necessario ao
ambiente de grade proporcionar mecanismos para realizar o controle deste recursos.
O principal objetivo do sistema de gerenciamento de recursos e escalonar o uso de
recursos de maneira eficiente.
Diversos trabalhos em grades computacionais apresentaram estrategias e modelos para
atacar os problemas e implementar as caracterısticas apresentadas. As proximas sessoes
apresentam alguns dos trabalho mais relevantes.
Globus
O Globus Toolkit (FOSTER; KESSELMAN, 1997; UNIVERSITY OF CHICAGO, 2005) e um
projeto que prove um conjunto de servicos e bibliotecas para dar suporte a infraestrutura
2.1 Grades Computacionais 11
e aplicacoes em grades. O Globus tem evoluıdo constantemente e vem sendo considerado
um padrao de facto para a computacao em grades. Esta sessao apresenta a versao 2 (GT2)
do Globus, que corresponde ao paradigma de grades computacionais da segunda geracao.
Atualmente o Globus esta em sua versao 3 (GT3), entretanto o GT3 impoe um paradigma
diferente, que nem sempre e facilmente adotado em todos cenarios de uso do Globus, assim
atualmente muitos ambientes de grades continuam utilizando o GT2.
O Globus e uma colecao de modulos que prove servicos de baixo custo para implementar
servicos de grade. Os principais componentes sao o GSI (Grid Security Infrastructure),
o GRAM (Globus Resource Allocation Manager) e o MDS (Monitoring and Discovering
System), descritos a seguir.
O GSI e base do sistema e e utilizado para: prover autenticacao e comunicacao segura
sobre uma rede aberta; suportar seguranca entre os diversos domınios administrativos,
evitando um sistem de seguranca centralizado; e suportar single sign-on para os usuarios
da grade, incluindo delegacao de credenciais.
O GSI e baseado em criptografia de chave publica, certificados X.509 e no protocolo de
comunicacao SSL (Secure Sockets Layer), com as extensoes necessarias para single sign-on
e delegacao. A implementacao do GSI esta em conformidade com a GSS-API (Generic
Security Service API), que e uma API padrao para seguranca de sistemas promovida pelo
IETF (Internet Engineering Task Force).
O GRAM e responsavel pela gerencia de recursos, ele prove uma interface padrao
para requisitar e utilizar sistemas remotos e para a submissao e controle de tarefas. O
objetivo e esconder a grande variedade de mecanismos de gerencia locais, fazendo com que
os desenvolvedores de aplicacoes somente necessitem conhecer a interface do GRAM. O
sistema de autorizacao do GRAM e baseado nas identidades GSI e em mecanismos para
mapear estas identidades para as polıticas locais de administracao de usuarios.
O MDS prove as ferramentas necessarias para construir um sistema de informacoes
2.1 Grades Computacionais 12
para grades baseado no servico de diretorio LDAP. O LDAP e utilizado para padronizar
os metodos de consulta as informacoes de sistema e para construir um espaco de nomes
uniforme para as informacoes fornecidas pelas muitas organizacoes que podem compor o
sistema.
O MDS e dividido nos modulos GIIS (Grid Index Infomation Service) e GRIS (Grid
Resource Information Service). O GRIS e o modulo responsavel por colher as informacoes
dos recursos, gerar os dados e proporcionar uma interface para consultar estas informacoes.
O GIIS prove um meio de agregar informacoes dos diversos GRIS que compoem o sistema,
servindo de repositorio de informacoes sobre todo o sistema, ou determinado sub-conjunto.
As aplicacoes entao podem consultar o GIIS em busca de informacoes, como recursos
disponıveis.
O Globus tambem implementa uma versao estendida do bem conhecido protocolo FTP
chamdo de GridFTP. As extensoes permitem o uso de protocolos de seguranca, acesso
parcial de arquivos e gerenciamento do paralelismo de transferencia em alta velocidade.
Alem dos elementos principais da arquitetura o Globus ainda prove diversos servicos
para facilitar o desenvolvimento de aplicacao. O GlobusIO oferece um servico de comu-
nicacao dentro da grade em um estilo similar a programacao em socket TCP/IP. O GASS
(Global Access to Secondary Storage) e utilizado para permitir o acesso a arquivos den-
tro da grade de forma simplificada, permitindo a reutilizacao de programas em linguagem
C padrao que fazem acesso a arquivo com pouca ou nenhuma modificacao. O DUROC
(Dynamically-Updated Request Online Coallocator) prove uma interface conveniente para
obter recursos e executar trabalhos atraves de multiplos gerenciadores de recursos de forma
coordenada.
2.1 Grades Computacionais 13
Legion
O Legion (GRIMSHAW; WULF, 1997) e um metasistema baseado em objetos, projetado
para construir um sistema de milhoes de nodos e trilhoes de objetos, interligados por redes
de alta velocidade. O projeto iniciou em 1993 e em 1997 teve sua primeira implementacao
divulgada.
O objetivo e dar aos usuarios a impressao de estar trabalhando em um unico compu-
tador com acesso a todos tipos de dados e recursos fısicos. Grupos de usuarios podem
construir grupos virtuais de trabalho para pesquisa colaborativa e troca de informacoes.
No Legion tudo e objeto: todos os recursos sao apresentados como Objetos Legion,
que sao processos ativos e independentes que respondem a invocacoes feitas por outros
objetos do sistema. A IDL (Interface Description Language) pode ser usada para descrever
a interface das classes de objetos.
Considerando o potencialmente grande numero de objetos que podem compor o sistema
, e oferecido um espaco de nomes controlado pelos usuarios chamado de context space, que
permite encontrar e usar objetos espalhados no sistema. Ainda, existe um esquema para
armazenar de forma persistente os objetos do sistema.
O Legion define a API para um conjunto de objetos nucleo (core objects) que supor-
tam servicos basicos como: nomeacao e ligacao; abstracao de recursos de processamento;
representacao persistente de objetos e ativacao, desativacao e delecao de objetos.
Condor
Muitos sistemas fazem uso de recursos heterogeneos distribuıdos geograficamente, se
aproximando dos objetivos dos grid. O Condor (UNIVERSITY OF WISCONSIN MADISON,
2005; LITZKOW; LIVNY; MUTKA, 1998) e um sistema de gerenciamento de recursos e tare-
fas, concebido para trabalhar com processamento em lote utilizando o poder de processa-
2.1 Grades Computacionais 14
mento de estacoes ociosas. O proposito do Condor e fornecer grande quantidade de poder
computacional a medio ou longo prazo.
O Condor recebe as tarefas dos usuarios e escolhe onde executa-las baseado em uma
determinada polıtica, e ainda prove os meios para acompanhar a execucao destas tarefas
e obter os resultados. As tarefas submetidas recebem um conjunto de restricoes como
necessidade de processamento e quantidade de memoria. Os donos das maquinas partici-
pantes do sistema tambem informam as restricoes de uso, por exemplo que so compartilha
sua maquina quando ela esta ociosa. O escalonador procura a melhor forma de casar os
requisitos das tarefas com os recursos disponıveis.
Um dos recursos interessantes do Condor e a capacidade de suspensao das tarefas
(LITZKOW et al., 1997). O mesmo mecanismo usado para a suspensao tambem permite que
uma tarefa seja migrada de uma maquina que deixou de estar ociosa para uma ociosa.
Entretanto o Condor surgiu para trabalhar em redes locais e questoes de seguranca e
de domınio administrativo local nao sao tratadas. O Condor-G (FREY et al., 2001) e uma
versao do Condor preparada para integrar-se com o Globus, permitindo a interligacao de
varios domınios Condor.
2.1.3 Terceira Geracao
A segunda geracao trouxe a interoperabilidade essencial para viabilizar a computacao
em grande escala, mas o progresso das solucoes deixou aparente novos aspectos que impli-
caram em modificacoes no paradigma.
Percebeu-se que seria valioso para aplicacoes nas grades reutilizar de forma flexıvel
componentes e recursos de informacao espalhados pela grade. A solucao para este problema
orientou o desenvolvimento dos ambientes de grades para modelos orientados a servico
com uma maior atencao para os metadados. O enfoque se deslocou da abordagem de
compartilhamento de recursos para a abordagem de compartilhamento de servicos (FOSTER;
2.1 Grades Computacionais 15
KESSELMAN; TUECKE, 2001; FOSTER et al., 2002).
A abordagem orientada a servicos por si so tem implicacoes na estrutura da informacao,
pois o emprego flexıvel de recursos distribuıdos pela grade para composicao de aplicacoes
tem requisitos proprios. E necessario ter informacoes sobre funcionalidade, disponibilidade
e interface para os varios componentes que vao compor a aplicacao, alem disto esta in-
formacao deve ter uma interpretacao pre-acordada para que possa ser processada de forma
automatica pelas maquinas.
Na terceira geracao sao introduzidos termos como colaboracao distribuıda e orga-
nizacoes virtuais (VOs) (FOSTER; KESSELMAN; TUECKE, 2001). O foco e a necessidade
de compartilhamento de recursos para solucao de problemas em conjunto. As organizacoes
virtuais sao portanto conjuntos de recursos sujeitos a um controle bastante claro de acesso.
Estas VOs sao provedores de recursos, por exemplo uma VO pode ser membro de um projeto
para construir uma aeronave e estar provendo os recursos computacionais para simular um
tunel de vento, ou ser um provedores de informacoes para tomada de decisoes estrategicas.
Enfim uma VO prove um recurso computacional qualquer que pode ser empregado para
resolver problemas de forma cooperativa.
Esta nova visao de grades computacionais se coaduna com o aumento da populari-
dade do paradigma de Web Services (IBM WEB SERVICES ARCHITECTURE TEAM, 2000),
uma tecnologia baseada em protocolos da Internet que visa ser padrao para arquiteturas
baseadas em servico.
Web Services
Os Web Services sao um paradigma de computacao distribuıda baseado em padroes da
Internet. Basicamente, um Web Service encapsula uma determinada tarefa, recebendo os
parametros pela rede e retornando o resultado. Os protocolos utilizados permitem que esses
servicos estejam nas mais diferentes plataformas e sejam escritos em qualquer linguagem.
2.1 Grades Computacionais 16
As mensagens trocadas sao escritas em XML (eXtensible Markup Language) (WORLD
WIDE WEB CONSORTIUM, 2005c), e o SOAP (Simple Object Access Protocol) prove um
mecanismo de transporte para estas mensagens (WORLD WIDE WEB CONSORTIUM, 2005a).
O XML e uma linguagem padronizada, extensıvel e estruturada, promovida pelo W3C
(World Wide Web Consortium). A independencia de dados, ou a separacao do conteudo de
sua apresentacao, e a caracterıstica essencial do XML. A apresentacao de um documento
XML pode variar de acordo com o uso.
O SOAP e utilizado para possibilitar a transferencia de dados em um sistema dis-
tribuıdo ou rede. E um protocolo baseado em XML, portanto e basicamente um conjunto
de esquemas em XML que descrevem a forma de transmitir mensagens pela rede, incluindo
o tipo de dados que as mensagens podem conter e a maneira em que devem estar estrutu-
radas. O protocolo mais comum para o SOAP e o HTTP, mas qualquer protocolo pode ser
utilizado.
Outra caracterıstica e que os Web Services tambem sejam auto-descritivos, provendo
informacao do que eles fazem e como podem ser utilizados. Estas descricoes geralmente
costumam ser feitas utilizando o WSDL (Web Services Description Language) (WORLD
WIDE WEB CONSORTIUM, 2005b).
Finalmente, e possıvel ter repositorios com informacoes sobre os Web Services dis-
ponıveis para as aplicacoes. Isto e feito pelo UDDI (Universal Description, Discovery and
Integration) (OASIS OPEN, 2005).
Todo Web Service e acompanhado de um WSDLfile que lista as capacidades do servico,
seu estado, localizacao e provedores. O arquivo WSDL define os tipos de mensagem que
ele pode enviar e receber, bem como os dados que a aplicacao chamadora deve prover.
2.1 Grades Computacionais 17
2.1.3.1 Open Grid Services Architecture
O OGSA (Open Grid Services Architecture) (FOSTER et al., 2002) e um esforco para
definir uma arquitetura padronizada para grades computacionais. O OGSA define uma
arquitetura baseada no princıpio que todos os recursos sao servicos.
O OGSA suporta a criacao, manutencao e arranjo dos servicos mantidos pelas VOs.
Um servico e definido com uma entidade de rede que prove alguma capacidade, como
recursos computacionais, recursos de armazenamento, rede, programas ou base de dados.
No OGSA um Grid Service e um Web Service que prove um conjunto de interfaces padrao
bem definido. Algumas interfaces padrao requeridas pelo OGSA sao:
Descoberta : Os clientes necessitam mecanismos para descobrir os servicos disponıveis e
para determinar as caracterısticas destes servicos de tal forma que possam configurar
a si e as suas requisicoes para estes servicos.
Criacao dinamica de servicos : A habilidade de criar e gerenciar automaticamente no-
vos servicos e fundamental na OGSA. Para isto e definido um servico de criacao
de servicos. O OGSA define uma interface padrao (factory) e uma semantica que
qualquer servico de criacao de servicos deve prover.
Gerenciamento de tempo de vida : Em um sistema que incorpora instancias de servicos
transientes e providas de estado (stateful) devem ser providos mecanismos para acom-
panhar o tempo de vida destes servicos. Assim, e possıvel determinar um tempo de
criacao para o servico, bem como uma validade.
Notificacao : Os objetos devem ser capazes de notificar uns ao outros de maneira assıncrona
as mudancas em seus estados.
Uma das caracterısticas do OGSA e suportar multiplos protocolos para a ligacao do
servico. As questoes pertinentes a autenticacao e invocacao do servico sao consideradas
como problemas dos protocolos de ligacao.
2.2 Programacao Paralela e Distribuıda com MPI 18
O OGSI (Open Grid Services Infrastructure) (TUECKE et al., 2003; GLOBAL GRID FO-
RUM, 2005) e um conjunto de especificacoes WSDL que define as interfaces padrao, com-
portamentos e esquemas para computacao em grades de acordo com o OGSA, ou seja, e a
especificacao em WSDL dos Grid Services.
O Globus 3.0 implementa o OGSA e as especificacoes definidas pelo OGSI, mas mantem
todo os servicos do GT2 como alternativas aos servicos GT3. A nova versao do Globus,
GT4, abandona o OGSI que se mostrou uma especificacao muito complexa.
2.2 Programacao Paralela e Distribuıda com MPI
Algumas aplicacoes podem ser paralelizadas, ou seja, divididas de forma a serem dis-
tribuıdas e serem executadas de forma distribuıda e simultanea em varios processadores.
O modelo de passagem de mensagens para computacao paralela se mostrou com um para-
digma expressivo e eficiente para programacao paralela. Inicialmente havia uma falta de
padronizacao, existindo muitas implementacoes destes modelos que em geral guardavam
uma mesma semantica. A partir de 1992 se organizou um forum com o objetivo de criar um
padrao que possibilitasse a portabilidade das aplicacoes que faziam uso de troca de men-
sagens. Como resultado, em 1994, foi publicada o MPI Standard 1.0 (MESSAGE PASSING
INTERFACE FORUM, 1994).
O MPI e uma interface de programacao para aplicacoes baseadas em troca de mensa-
gens. O MPI inclui operacoes para troca de mensagem ponto-a-ponto como o MPISend e
MPIRecv. Para grupos de processadores, o MPI prove as operacoes coletivas. Os proces-
sadores sao identificados por numeros e estes identificadores sao chamados ranks. Alem do
rank os processadores podem ser identificados de acordo com topologias virtuais, relacio-
nadas com a semantica da aplicacao.
O MPICH (GROPP et al., 1996) e uma das implementacoes mais populares e testadas do
padrao de interface para troca de mensagens. Os objetivos principais do MPICH sao atingir
2.2 Programacao Paralela e Distribuıda com MPI 19
alto desempenho e portabilidade. Atualmente o MPICH e uma implementacao completa
do padrao MPI com extensoes para suportar funcoes de I/O paralelo definido no padrao
MPI2 (MESSAGE PASSING INTERFACE FORUM, 1997).
O MPICH-G2 (FOSTER; KARONIS, 1998; KARONIS; TOONEN; FOSTER, 2003) e a imple-
mentacao da biblioteca MPICH para ambientes em grade baseada no Globus. Os servicos
do Globus sao utilizados para autenticacao, autorizacao, comunicacao e submissao de traba-
lhos. Uma vantagem deste modelo e estar baseada em um codigo ja bastante desenvolvido
e testado que e o do MPICH. A estrategia do MPICH-G2 para melhorar o desempenho e
utilizar as bibliotecas para comunicacao internas quando estas estiverem disponıveis e so-
mente fazer a comunicacao atraves do Globus quando os processos estiverem em diferentes
domınios.
Antes de iniciar uma aplicacao MPICH-G2 o usuario usa o GSI para obter uma cre-
dencial para se autenticar. O usuario tambem pode usar o MDS para selecionar os com-
putadores que serao utilizados, de acordo com configuracao, disponibilidade e conectivi-
dade de rede. Uma vez autenticado, o usuario requisita a criacao da computacao MPI.
O MPICH-G2 usa o RSL (Resource Specification Language) para descrever os trabalhos
a serem executados. Baseados nestas estruturas o MPICH-G2 chama a biblioteca de co-
alocacao distribuıda DUROC para escalonar e iniciar a aplicacao pelos varios computadores
especificados pelo usuario. O DUROC usa o GRAM para iniciar e gerenciar as subcom-
putacoes MPI. Para cada subcomputacao o DUROC gera uma requisicao para um servidor
GRAM que autentica o usuario, realiza a autenticacao local e interage com o escalonador
local para iniciar os processos. O GASS e utilizado para transferir os executaveis em MPI
e colher os resultados das saıdas e entradas padrao.
Uma vez iniciado, o MPICH-G2 seleciona o meio mais eficiente de computacao possıvel
entre dois processos, usando as bibliotecas MPI especıficas ou o Globus IO para TCP. Nao
existe entretanto meio de aglutinar as conexoes entre domınios distintos, assim, podemos
ter centenas ou milhares de conexoes Globus IO passando entre os domınios. Alem disto
2.2 Programacao Paralela e Distribuıda com MPI 20
todo participante da computacao distribuıda necessita ter um IP valido na Internet. Este
e um problema, especialmente porque muitas vezes em clusters somente uma das maquinas
possui um endereco valido.
Outra caracterıstica importante do MPICH-G2 e a utilizacao das informacoes especifi-
cadas no script RSL para criar aglutinamento em multiplos nıveis dos processos baseados
na topologia da rede. Alem do rank, cada processo tem um identificador de profundidade
topologica e uma cor. Sao quatro nıveis de profundidade topologica e em cada nıvel to-
pologico, um processo MPI que tem a mesma cor pode se comunicar no nıvel de rede.
Quanto a aplicacao, o MPICH esta direcionado principalmente a interligar centros de pro-
cessamento paralelo. O problema de escala para interligar um grande numero de pequenos
centros de computacao ou mesmo computadores individuais nao e avaliado.
O PACX-MPI (Parallel Computer eXtension) (BEISEL; GABRIEL; RESCH, 1997) e uma
implementacao do padrao do MPI que objetiva o acoplamento de sistema de computacao
de alto desempenho atraves de grades computacionais. O PACX-MPI e baseado em tres
conceitos fundamentais: utilizacao de dois nıveis hierarquicos utilizando bibliotecas de co-
municacao totalmente independentes para cada um destes nıveis; utilizacao das bibliotecas
especıficas locais para as operacoes internas; e, utilizacao de servidores de comunicacao. Os
dois primeiros conceitos sao bastante similares aos apresentados pelo MPICH-G2, a grande
diferenca e a utilizacao dos servidores de comunicacao entre os diferentes domınios para
empacotar as comunicacoes e evitar milhares de conexoes entre os sistemas. Alem disto a
existencia de um servidor diminui problemas com firewalls e com a necessidade de todos os
participantes da computacao precisarem enderecos validos na rede.
O PACX-MPI nao utiliza uma infraestrutura de grade para tratar problemas como
identificacao, autenticacao e submissao dos processos. Novamente e um modelo mais di-
recionado a interligacao de sıtios de processamento local, onde as regras de seguranca sao
acordadas de forma nao automatica pelos gerentes.
2.2 Programacao Paralela e Distribuıda com MPI 21
O MagPIe (KIELMANN et al., 1999) (magpie e um passaro que sobrevoa areas extensas
coletando coisas) e uma biblioteca MPI baseada no MPICH. Este trabalho considera que as
operacoes de comunicacao coletivas sao construıdas levando em consideracao redes locais ou
redes de sistema com uma latencia muito menor que as redes WAN (Wide Area Networks).
O principal objetivo do MagPIe e otimizar as operacoes de comunicacao coletivas em rede
WAN. Os algoritmos propostos no MagPIe levam em conta a hierarquia presente nas WANs
e procura diminuir o trafego pelo enlaces mais lentos. Sao apresentados algoritmos para
as 14 operacoes coletivas do MPI. Outro objetivo do MagPIe e evitar qualquer tipo de
modificacao nos programas tradicionais de MPI.
Resultados de simulacao mostram melhorias de 4 a 8 vezes no desempenho das operacoes
coletivas. A metodologia empregada tambem evita a necessidade de modificacoes nos
codigos escritos utilizando o MPI. O MagPIe demonstra que no ambiente de grades pode
se obter melhorias de desempenho otimizando as implementacoes das operacoes coletivas.
Em (SUPINSKI; KARONIS, 1999) e abordada a questao de como avaliar o desempenho de di-
fusoes em ambiente de grade. Em (GENAUD; GIERSCH; VIVIEN, 2003; KARONIS et al., 2000)
sao apresentadas abordagens para otimizar as operacoes coletivas em ambientes paralelos.
Em sistemas compostos por milhoes de nodos a falha ou desconexao destes nodos e um
evento frequente e deve ser considerado. Um estudo de disponibilidade com computadores
pessoais (BOLOSKY et al., 2000) dentro de uma rede de 64 mil maquinas, demonstrou que
5% a 10% das maquinas tornam-se inacessıveis no perıodo de 24 horas. Finalmente um
estudo do tempo de vida determinou que 1/3 das maquinas e desativada no perıodo de 24
horas. Esta situacao tende a ser ainda pior no ambiente de Internet. Desta forma, prover
o MPI de tolerancia a falhas e um requisito para executar com sucesso aplicacoes paralelas
no ambiente de grades. Atualmente existem diversas arquiteturas para prover tolerancia
a falhas usando diferentes tecnicas. Os diversos sistemas de tolerancia a falhas podem ser
classificados basicamente pelo nıvel em que se introduzem na pilha de software ou pela
tecnica de tolerancia a falhas empregada.
2.2 Programacao Paralela e Distribuıda com MPI 22
Quanto ao nıvel de introducao do mecanismo de tolerancia a falhas podemos ter os
seguintes casos: o programador da aplicacao salva periodicamente os resultados inter-
mediarios em um meio confiavel e os recupera em caso de necessidade; se instrumentaliza
o MPI para receber notificacoes de falha e aceitar reconfiguracoes do contexto de comu-
nicacao; se oferece uma implementacao do MPI que prove deteccao e recuperacao de falhas
de forma totalmente automatica. As implementacoes transparentes tem a grande vantagem
de permitir a migracao de aplicacoes ja existentes sem necessidade de modificacao.
A implementacao desse tipo de ambiente depende da utilizacao de estrategias de check-
point e/ou registro de mensagens (message logging) (ELNOZAHY et al., 2002). O checkpoint
(CHANDY; LAMPORT, 1985) e uma estrategia que armazena o estado do processo em meio
de armazenamento estavel para proposito de migracao ou recuperacao voltando a um es-
tado anterior (rollback). Um processo interrompido pode continuar a execucao a partir do
ultimo checkpoint.
A estrategia de checkpoint global pode ser dividida em: nao coordenado, induzido por
comunicacao e coordenado. Nos protocolos de checkpoint coordenado, todos os processos
coordenam seus checkpoints de forma que o estado global do sistema, composto pelos check-
points de todos os processos, seja coerente. Nos modelos de checkpoint nao coordenado,
os checkpoints de cada processo sao executados de forma independente. O problema deste
enfoque e que pode ser necessario realizar roolbacks encadeados ate a situacao inicial do
processamento para obter um estado consistente.
As estrategias de checkpoint induzido por comunicacao tentam ser uma versao in-
termediaria entre as estrategias de checkpoint coordenado e o nao coordenado. As de-
pendencias de causalidade sao analisadas em todas mensagens, forcando o checkpoint de
alguns processos quando for detectado algum risco de inconsistencia. O problema desta
estrategia e a falta de escalabilidade, que pode levar a um grande numero de checkpoints, e
os requisitos de frequencia e armazenamentos dos checkpoints que podem ser imprevisıveis.
2.2 Programacao Paralela e Distribuıda com MPI 23
Outra tecnica que pode ser empregada para obter tolerancia a falha e o registro de
mensagem. Esta tecnica se baseia na possibilidade de repetir a computacao realizada
submetendo os processos ao mesmo indeterminismo. No caso de um sistema de troca de
mensagens os elementos de indeterminismo sao justamente as mensagens recebidas pelos
processos.
As estrategias de registro de mensagem podem ser classificas em tres modelos (ALVISI;
MARZULLO, 1995). No registro pessimista os processos precisam aguardar que o registro
da mensagem seja feito em meio permanente, para so entao poder produzir os resultados
consequentes da mensagem. Isto simplifica a recuperacao mas impoe alto custo para as
operacoes livres de falha. No modelo otimista a aplicacao nao fica aguardando o registro
da mensagem, entretanto esta estrategia pode tornar necessaria a realizacao de rollback
em nodos que nao falharam, mas apresenta melhor desempenho em ambientes livres de
falha. A estrategia de registro causal tenta conciliar as duas estrategias, realizando registros
locais das mensagens enviadas e da relacao causal delas. Em (BOUTEILLER et al., 2003b)
e apresentada uma avaliacao sobre a eficiencia das estrategias de checkpoint e registro de
mensagens para MPI.
O CoCheck (STELLNER, 1996) e um dos primeiro esforcos para ter uma implementacao
do MPI confiavel. O CoCheck estende o mecanismos de checkpoint para um unico processo
do Condor para um sistema distribuıdo de troca de mensagens. O CoCheck e baseado
em uma implementacao propria de MPI. Um coordenador central confiavel e mantido para
realizar os procedimentos de checkpoint e rollback. Para evitar os problemas conhecidos
de inconsistencia global ou efeito domino o CoCheck descarrega todas as mensagens em
transito antes de realizar o checkpoint. Um dos problemas desta estrategia e o custo para
descarregar todas as mensagens. Outra deficiencia e a existencia de um coordenador central,
que pode criar um gargalo tanto para a execucao do checkpoint como para o rollback.
O Starfish (AGBARIA; FRIEDMAN, 1999) prove um ambiente de tolerancia a falhas ba-
seado no Ensemble (HAYDEN, 1997), que e um ambiente de comunicacao em grupo. Todos
2.2 Programacao Paralela e Distribuıda com MPI 24
processos MPI abrigam um daemon que participa de um grupo. As comunicacoes de con-
trole, notificacao de falhas e demais mensagens internas sao feitas utilizando as primitivas
de comunicacao de grupo do Ensemble. Uma vantagem do Starfish e a flexibilidade. A
abordagem utilizada permite que seja possıvel optar, por exemplo, em usar checkpoint co-
ordenado ou nao-coordenado. Tambem pode ser usado um modelo de tolerancia a falhas
transparente ou no nıvel do usuario.
O MPI/FT (BATCH et al., 2001) prove servicos de deteccao e recuperacao para os
processos MPI, estes servicos sao projetados para minimizar o overhead de acordo com
o modelo de execucao de aplicacao. Os modelos de execucao de aplicacao sao abstracoes
derivadas de combinacoes de topologias e tecnicas de programacao paralela. De acordo com
o modelo e utilizado checkpoint e ou redundancia de tarefas para prover a tolerancia a falhas.
A opcao por redundancia de tarefa tem o inconveniente da necessidade de implementar
tecnicas de votacao. Na arquitetura do MPI/FT tambem estao previstos diversos sensores
usados para deteccao de falhas no nıvel de aplicacao, MPI, rede ou sistema operacional.
Um coordenador central monitora o progresso da aplicacao, registra as mensagens e reinicia
os processos falhos a partir de um checkpoint.
O MPI-FT(LOUCA et al., 1991) e baseado na implementacao LAM-MPI (SQUYRES;
LUMSDAINE, 2003) do padrao MPI, e utiliza processos de monitoramento chamados obser-
vadores para prover deteccao de falhas e mecanismos de recuperacao no nıvel de processo
do MPI. O detector de falhas e baseado na verificacao da existencia dos processos MPI
nos nodos. Sao propostas duas estrategias de registro de mensagens, uma otimista, des-
centralizada, requerendo que cada processo MPI armazene as mensagens enviadas; outra
pessimista, centralizada, com todo registro no observador. Para recuperacao o MPI-FT
cria novos processos para substituir os processos falhos e reinicia a execucao. A execucao
sempre e feita do inıcio, o que implica em alto custo para a recuperacao e requer alta ca-
pacidade de armazenamento para as mensagens. A vantagem desta estrategia e nao haver
a necessidade de realizar checkpoint.
2.2 Programacao Paralela e Distribuıda com MPI 25
O FT-MPI (FAGG; DONGARRA, 2000) trata as falhas no nıvel de comunicacao do MPI
e deixa que a aplicacao gerencie a recuperacao. Quando uma falha e detectada todos os
processos da comunicacao sao informados sobre a falha. Esta informacao e transmitida
para a aplicacao atraves de retorno na chamada MPI. Entao a aplicacao pode tomar as
decisoes apropriadas e executar as operacoes de correcao. A vantagem desta abordagem e o
desempenho, ja que nao ha praticamente overhead envolvido. Entretanto e preciso adaptar
as aplicacoes MPI para fazer tolerancia a falhas.
O MPICH-V (BOLSICA et al., 2000) e um ambiente para tolerancia a falhas baseado em
checkpoint/rollback e registro pessimista distribuıdo de mensagens . O MPICH-V e cons-
truıdo para ser um projeto adaptavel ao maior numero de implementacoes do padrao MPI
e permitir execucao de aplicacoes sobre computadores voluntarios da Internet. O ultimo
objetivo impoe requisitos de tolerancia a falhas transparente, ou seja, a nao necessidade
de modificar as aplicacoes MPI, ser escalavel para um grande numero de nodos e envolver
apenas bibliotecas no nıvel do usuario. Considerando o ambiente de Internet de grande ins-
tabilidade dos nodos, o MPICH-V trabalha com o conceito de volatilidade. A volatilidade
e relacionado com o fato de que os nodos considerados falhos sao substituıdos por outros e
os resultados produzidos depois de sua desconexao nao sao utilizados na computacao MPI
em que ele participava.
A arquitetura do MPICH-V e composta pelas seguintes entidades: Dispatchers, Memoria
de Canal (CM - Channel Memory ), Servidor de Checkpoint (CS - Check Point Server) e os
nodos que realizam a computacao propriamente dita. Os CMs sao responsaveis por prover
o registro de mensagens, ou seja, guardar o contexto de comunicacao. Os CMs tunelam
e servem de repositorios para as mensagens do sistema. Cada CM e responsavel por um
conjunto de nodos, assim para cada nodo existe um unico CM responsavel chamado de
home CM. Todas mensagens enviadas para um nodo sao enviadas por seu home CM. Para
cada nodo, o contexto de execucao e salvo, periodicamente provocado pela recepcao de um
sinal, no CS.
2.2 Programacao Paralela e Distribuıda com MPI 26
O dispatcher faz a coordenacao dos recursos necessarios para realizar uma determinada
computacao. Para isto atribui nodos para executar o CM, CS e os processo do MPI. Alem
disto o dispatcher precisa armazenar o mapa de atribuicao dos CMs e CSs em um Registro
de Servico Estavel. Assim quando um nodo executa uma aplicacao MPI ele primeiro
contacta o Servico de Registro que resolve o endereco do CS e CM de acordo com seu rank
no MPI. O dispatcher tambem e responsavel por realizar a deteccao de falhas. Durante a
execucao dos testes os nodos enviam heartbeats para ele, quando um timeout ocorre uma
nova tarefa MPI e lancada para substituir a falha, e os contextos de mensagem e execucao
sao restaurados. Quanto ao nodo falho, caso tente se reintegrar ao sistema sera reintegrado
como um novo nodo, ja que ele ja foi substituıdo na computacao.
O MPICH-V2 (BOUTEILLER et al., 2003a) e a geracao seguinte do MPICH-V, tambem
sendo baseado em checkpoint nao coordenado e registro de mensagens pessimista. O
MPICH-V2 se preocupa com o fato de que o CM impoe um grande impacto no desem-
penho, tornando alto o custo da tolerancia a falhas, ja que para se obter um desempenho
satisfatorio existe a necessidade de utilizar-se um grande numero de CMs. A estrategia do
MPICH-V2 e dividir o registro das mensagens em duas partes: a mensagem propriamente
dita e registrada no nodo de processamento que a esta gerando; o evento correspondente ao
envio da mensagem e armazenado em um registrador de eventos confiavel. A quantidade de
informacao armazenada no registrador de eventos e proporcional ao numero de mensagens
transmitidas e nao ao tamanho.
O registro dos eventos serve para armazenar as informacoes de dependencia entre as
mensagens trocadas pelos processadores. Um relogio logico e usado para criar uma ordem
nestas mensagens. O objetivo e poder repetir as comunicacoes feitas entre os nodos e
reconstruir informacoes perdidas em caso de falha, ja que as mensagens sao registradas
apenas localmente. A estrategia do MPICH-V2 e uma melhoria consideravel sob a versao
anterior, entretanto a arquitetura ainda continua necessitando elementos confiaveis como
o registrador de eventos, o dispatcher e o CSs. O que cria problemas de escalabilidade e
2.3 Redes Overlay Peer-to-Peer 27
deixar o sistema vulneravel a falhas destes componentes.
2.3 Redes Overlay Peer-to-Peer
Recentemente, redes overlay tem sido propostas em sistemas P2P como alternativa
para solucionar os problemas de escalabilidade (DOVAL; O’MAHONY, 2003). A computacao
P2P e uma abordagem para compartilhar grande quantidade de recursos. Na computacao
P2P as maquinas compartilham dados ou recursos, como ciclos de computacao ociosos
ou capacidade de armazenamento, via Internet ou redes privadas. Em uma rede P2P a
nocao de cliente e servidor e relativa, de forma que os processos apresentam funcoes tanto
de clientes como de servidores. Assim as maquinas podem se comunicar diretamente e
gerenciar suas tarefas sem utilizar servidores centrais. Isto permite que a computacao P2P
seja mais escalavel que o modelo tradicional cliente-servidor, apresentando-se como uma
das melhores abordagens para criar redes globais de compartilhamento de recursos.
Encontramos redes overlay em sistemas P2P implementando as mais diversas topo-
logias, como: malha, no Pastry (ROWSTRON; DRUSCHEL, 2001) e Tapestry (ZHAO et al.,
2004); anel, no Chord (STOICA et al., 2001); torus d-dimensional, no CAN (RATNASAMY et
al., 2001); e borboleta em (FIAT; SAIA, 2002) e (SAIA et al., 2002). Estas redes overlay orga-
nizam a rede subjacente de forma a facilitar a busca de objetos armazenados nos nodos que
compoem o sistema. Esta estrategia melhora a escalabilidade do sistema, evitando o uso
de algoritmos de inundacao para propagar requisicoes de busca, por exemplo. As tabelas
hash distribuıdas sao uma das tecnicas mais comuns empregadas para construir estas redes
(BALAKRISHNAN et al., 2003).
O CAN e uma das propostas de implementacao distribuıda de tabelas hash. O CAN
utiliza uma abordagem geometrica para organizar os nodos. Sao atribuıdas posicoes para
os nodos em um espaco d-dimensional em um d−torus. Para organizar os nodos e atribuir
2.3 Redes Overlay Peer-to-Peer 28
objetos para compartilhamento, o CAN usa funcoes d-hash, o que permite ao nodo obter
uma chave espaco d para si proprio. Cada nodo mantem uma tabela com O(d) entradas e
qualquer nodo pode ser alcancado em O(dN1/d) saltos, em um sistema com N nodos. Desta
forma, a tabela de roteamento nao cresce de acordo com o numero de nodos no sistema, mas
o numero de saltos necessarios para atingir o destino e maior que logN , especificamente
O(dN1/d).
O Pastry e uma rede P2P para localizacao de objetos e roteamento de mensagens. No
Pastry cada nodo e identificado por um identificador unico de 128-bits. Este identificador
e utilizado para indicar a posicao do nodo em um espaco circular. Cada aplicacao pode
atribuir um unico identificador, ou chave, para um objeto. Esta chave e mapeada para
um nodo na rede e as mensagens sao roteadas pelos nodos cujos identificadores estao
numericamente mais proximos da chave.
Considerando uma rede com N nodos, o Pastry pode rotear uma mensagem para o
nodo mais proximo de uma dada chave com um numero de saltos na ordem de O(logN),
mantendo uma tabela de roteamento com um numero de entradas na ordem de O(logN)
linhas. As entradas em uma linha n da tabela, se referem aos nodos cujo identificador com-
partilha os n primeiros dıgitos, mas nao o (n+ 1)−esimo bit, com o nodo atual. Associado
a cada entrada da tabela de roteamento esta o endereco IP dos nodos mais proximo (a
proximidade e estimada pelo tempo de round trip). Alem da tabela de roteamento, cada
nodo mantem uma lista dos vizinhos imediatos, chamada leaf set.
As mensagens sao roteadas de acordo com a maior coincidencia com a chave destino.
Se a chave estiver na faixa dos identificadores contidos no leaf set, entao a mensagem e
roteada para o nodo cujo identificador e o mais proximo da chave. Caso contrario, o nodo
busca em sua tabela pelo nodo cujo identificador possua um um prefixo com um numero
maior de bits coincidentes com a chave do que o nodo atual. Se este nodo nao existir,
a mensagem e enviada para um nodo cujo identificador possua um prefixo com o mesmo
numero de bits coincidentes com a chave que o nodo atual, mas que esteja numericamente
2.3 Redes Overlay Peer-to-Peer 29
mais proximo da chave.
O Tapestry e bastante similar ao Pastry, mas tem uma abordagem diferente para ma-
pear as chaves para os nodos. No Tapestry nao existe o leaf set e a vizinhanca de nodos
nao e conhecida. Os identificadores tem 160 bits que sao divididos em dıgitos de 16 bits.
As mensagens sao encaminhadas sucessivamente para nodos com um identificadores com
numero de dıgitos coincidentes progressivamente maiores. Quando a tabela de roteamento
de um nodo nao tem uma entrada para um nodo com o n−esimo dıgito coincidente, a
mensagem e encaminhada para o nodo cujo identificador possua o valor mais proximo no
n−esimo dıgito. Este procedimento e chamado surrogate routing e mapeia as chaves para
um unico nodo com um identificador similar. O numero esperado de saltos de roteamento
e log16N .
O Chord usa um espaco circular de identificadores de 160 bits para organizar os nodos.
Ao contrario do Pastry e Tapestry, o Chord encaminha mensagens apenas no sentido horario
do espaco circular de identificadores. Ao inves do roteamento baseado em prefixo do Pastry,
o Chord mantem uma tabela chamada de finger table. Esta tabela contem o identificador e o
endereco IP de ate 160 nodos. A i−esima entrada na finger table do nodo n se refere ao nodo
que sucede n em pelo menos em n+2i−1 saltos no espaco circular de identificadores. Assim,
a primeira entrada aponta para os sucessor direto do nodo n, e as entradas subsequentes se
referem a nodos com distancia repetidamente dobradas de n. Cada nodo tambem mantem
ponteiros para seus predecessores e para os seus k sucessores no espaco de identificadores.
O numero de saltos esperados para rotear uma mensagem no Chord e 1/2log2N .
As redes overlay P2P descritas acima apresentam uma abordagem distinta da rede
overlay proposta neste trabalho. Estao destinadas para armazenar e recuperar conteudo
organizando a topologia do sistema em funcao das chaves dos objetos armazenados. O
HyperBone visa oferecer servicos de comunicacao e monitoracao permitindo a execucao de
aplicacoes distribuıdas, especialmente em sistemas instaveis. A instabilidade do sistema
e abordada por alguns trabalhos em P2P (FIAT; SAIA, 2002; SAIA et al., 2002), mas no-
2.3 Redes Overlay Peer-to-Peer 30
vamente estes trabalhos sao direcionadas especificamente para a busca de informacao, o
foco e como manter acessıvel toda ou parte da informacao armazenada na rede mesmo em
caso de falha dos nodos. A questao da deteccao de falhas em redes overlay e tratada em
(ZHUANG et al., 2005), onde sao avaliadas diversas classes de algoritmos. O estudo emprega
modelos analıticos, simulacao e experimentacao usando metricas como tempo de deteccao,
probabilidade de falsos positivos, overhead de controle e taxa de perda de pacotes. As
conclusoes deste trabalho evidenciam a importancia do compartilhamento de informacao
de monitoracao e a necessidade de sistemas eficientes de monitoracao.
Quanto ao uso de hipercubos como topologia para rede virtual, podemos citar o Hyper-
cup (SCHLOSSER et al., 2002). O algoritmo proposto naquele trabalho baseia-se em posicoes
livres e ocupadas em um hipercubo. Um nodo que funciona como peer de uma rede P2P
e deseja se integrar ao sistema faz um pedido de entrada e recebe uma posicao livre no
hipercubo. Entao, esta posicao se torna ocupada ate que este nodo deixe o sistema. Para
manter a integridade do sistema uma mensagem de broadcast e enviada para avisar todos
os nodos que uma posicao do hipercubo se tornou ocupada ou vazia. Um problema no Hy-
percup e que o sistema somente e capaz de tratar a ocorrencia de um unico evento, entrada
ou saıda de um unico nodo a cada vez: o tratamento de multiplos eventos simultaneos e
apontada como trabalho futuro.
31
3 Diagnostico Distribuıdo
Considere um sistema com N nodos. Assuma que o sistema e totalmente conectado,
ou seja, existe um enlace de comunicacao entre qualquer par de nodos, considere ainda que
os nodos podem estar falhos ou sem-falhas e que os enlaces de comunicacao nao falham. O
objetivo do diagnostico distribuıdo em nıvel de sistema e permitir que todos os nodos sem-
falhas determinem o estado, falho ou sem-falhas, de todos os nodos do sistema. Os nodos
em um sistema de diagnostico sao capazes de testar outros nodos e determinar seu estado
corretamente. Utilizando algoritmos de diagnostico distribuıdo e possıvel construir siste-
mas de monitoracao de rede tolerante a falhas (BIANCHINI; BUSKENS, 1991). Este capıtulo
apresenta conceitos e algoritmos de diagnostico em nıvel de sistema, que serao posterior-
mente utilizados na apresentacao do algoritmo DiVHA, utilizado para a manutencao na
topologia virtual do HyperBone.
3.1 O Modelo PMC
O modelo PMC foi proposto por Preparata, Metze e Chien, o nome do modelo vem
das iniciais dos nomes dos autores (PREPARATA; CHIEN, 1967). O modelo PMC utiliza a
teoria de grafos em seu formalismo, os vertices representam unidades do sistema capazes
de testar outras unidades, ou nodos, e as arestas direcionadas indicam os testes realizados.
Uma aresta saindo do nodo u para o nodo v significa que o nodo u testa o nodo v. Cada
teste corresponde a um estımulo enviado cuja resposta sera classificada em pass ou fail
mapeados respectivamente para 0 e 1 nos pesos das arestas. O conjunto destes resultados
3.1 O Modelo PMC 32
e definido como sendo a sındrome do sistema.
Para determinar o estado de cada nodo do sistema e necessario analisar a sındrome,
onde resume-se a tarefa de diagnostico. Nem sempre a existencia de um teste com o
resultado fail significa que o nodo testado e falho. Isto porque o resultado de um teste so
deve ser considerado caso o nodo testador nao esteja falho. Se o nodo testador for falho o
resultado do teste nao e previsıvel e nao informa nada a respeito do nodo testado.
No modelo PMC nao sao consideradas falhas de enlaces e o sistema e representado por
um grafo completo. Os testes realizados sao fixados previamente e o conjunto destes testes
determina se um sistema pode ou nao ser diagnosticado. Em (PREPARATA; CHIEN, 1967;
HAKIMI; AMIN, 1974) sao examinadas as condicoes necessarias e suficientes para que um
conjunto de testes permita obter o diagnostico correto do sistema.
Um sistema e dito t-diagnosticavel em um passo quando e possıvel identificar todas
as unidades falhas atraves da analise da sındrome. Para que um sistema com N nodos
seja t-diagnosticavel em um passo, o numero de unidades falhas, t, nao pode ultrapassar
N−12
. Alem disto cada unidade deve ser testada por pelo menos t outras unidades. Entao
num sistema com N = 2t + 1 sao necessarios N ∗ N−12
testes, portanto o numero de testes
requeridos e O(N2).
A estrategia de fixar previamente todos os testes pode dificultar o diagnostico, pois
e preciso atribuir antecipadamente testes que compensem os testes que deixam de ser
executados pelas unidades com falhas. Desta forma, foram criados os algoritmos adaptativos
(HAKIMI; NAKAJIMA, 1984) onde os testes nao sao fixos, sendo determinados de acordo com
os resultados dos testes realizados anteriormente.
Outra caracterıstica do modelo PMC e a necessidade de um nodo que receba todos os
resultados dos testes e realize o diagnostico. A ideia de eliminar esta unidade, distribuindo
a tarefa de diagnostico entre os nodos que realizam os testes e que fez surgir os algoritmos
distribuıdos (HOSSEINI; KUHL; REDDY, 1984).
3.2 O Algoritmo Adaptive-DSD 33
3.2 O Algoritmo Adaptive-DSD
O algoritmo Adaptive Distributed Sytem-level Diagnosis (ADSD) (BIANCHINI; BUS-
KENS, 1991, 1992) e um algoritmo de diagnostico em nıvel de sistema ao mesmo tempo
distribuıdo e adaptativo criado por Bianchini e Buskens. Por ser distribuıdo, nao existe
uma unidade central para realizacao do diagnostico. Por ser adaptativo, a configuracao dos
testes vai alterando-se durante a execucao do algoritmo.
Os algoritmos adaptativos possuem a nocao de rodadas de testes (testing rounds), que
e o perıodo de tempo necessario para que todos os nodos sem-falhas executem os testes
que lhe foram atribuıdos. No algoritmo ADSD a rodada de testes e definida como o tempo
necessario para que todos os nodos sem-falha do sistema testem pelo menos um nodo sem-
falhas. A latencia e definida como o numero de rodadas de testes necessarias para que todos
os nodos do sistema realizem o diagnostico de um evento ocorrido. Um evento e a transicao
de um nodo do estado de sem-falhas para falho ou do estado de falho para sem-falhas. O
numero de testes realizados a cada rodada de testes e a latencia sao medidas utilizadas
para comparar a eficiencia de algoritmos de diagnostico adaptativos.
No algoritmo ADSD cada nodo testa outros nodos ate encontrar um nodo sem-falhas do
qual colhe informacoes para atualizar suas informacoes de diagnostico. Uma consequencia
da estrategia de testes do ADSD e que cada nodo e testado por um unico nodo sem-falhas
a cada rodada.
Em um sistema com N nodos executando o algoritmo ADSD, os nodos sao identificados
como u1, u2,...,uN . O nodo ui tambem e chamado nodo i. A adicao usada e modulo N ,
de modo que o nodo uN e seguido por uN + 1 que e u0, formando um anel de nodos. Os
testes sao realizados sequencialmente, assim ui testa ui+1 e seguintes ate encontrar um
nodo sem-falhas, entao atualiza sua informacao local de diagnostico com as informacoes
lidas do nodo testado. Estas informacoes sao resultantes tanto de testes realizados pelo
nodo testado como de informacoes lidas de outros nodos.
3.3 O Algoritmo Hi-ADSD 34
0
2
6
7
4
3
5
1
Figura 2: Sistema executando o algoritmo ADSD.
A figura 2 mostra um sistema executando o algoritmo ADSD. Os nodos assinalados com
“X” estao falhos e os nao assinalados sem-falhas. Em uma rodada de testes cada nodo testa
sequencialmente seus sucesssores. O nodo 0, por exemplo, testa o nodo 1, descobrindo que
o nodo 1 esta falho, entao testa o nodo 2, sem-falhas, lendo as informacoes de diagnostico
dele. De forma analoga comportam-se os nodos 2, 3, 6 e 7.
Em termos de quantidade de testes a cada rodada, o algoritmo ADSD e considerado
eficiente sendo executados no maximo N testes a cada rodada. Quanto a latencia, podem
ser necessarias ate N rodadas para que todos os nodos realizem o diagnostico de um evento.
Isto ocorre porque a informacao sobre o estado de um nodo e passada para apenas um novo
nodo a cada rodada. Como em cada rodada os testes estao sendo feitos sequencialmente
por u0, u1, etc, se o nodo uN falhar, entao o nodo uN−1 detecta a falha, mas apenas na
outra rodada o nodo uN−2 le informacoes de uN−1 e descobre a falha em uN , da mesma
forma os demais nodos vao obtendo a informacao nas rodadas de teses seguintes. Com isto,
podem ser necessarias N rodadas de testes ate a informacao da falha de uN chegar a u0.
3.3 O Algoritmo Hi-ADSD
O algoritmo Hierarchical Adaptive Distributed System-Level Diagnosis (Hi-ADSD) (DU-
ARTE Jr.; NANYA, 1998) e hierarquico, alem de ser distribuıdo e adaptativo, realizando testes
3.3 O Algoritmo Hi-ADSD 35
baseados numa estrategia de dividir para conquistar.
A hierarquizacao dos testes e alcancada utilizando o conceito de clusters. Os clusters
sao conjuntos de nodos testados a cada rodada, o tamanho aumenta progressivamente a
cada rodada sempre sendo uma potencia de dois. Um cluster de p nodos nj, ..., nj+p−1 onde
j MODp = 0 e p e uma potencia de dois, e definido recursivamente como um nodo, quando
p = 1; ou como a uniao de dois clusters, um contendo os nodos nj, ..., nj+p/2−1 e outro
nj+p/2, ..., nj+p−1. A figura 3 mostra um sistema de oito nodos organizado em clusters.
0 1
7632
4 5
Figura 3: Sistema de 8 nodos agrupados em clusters no algoritmo Hi-ADSD.
Um nodo sem-falhas inicialmente realiza testes em clusters de tamanho 1 (20), nas
proximas rodadas os clusters tem tamanho 2 (21), 4 (22), 8 (23) ate atingir N/2 (2(log2N)−1)
nodos. A lista ordenada de nodos testados por um determinado nodo i em um cluster de
tamanho 2s−1 e dada por Ci,s. A expressao que caracteriza Ci,s e dada como segue:
Ci,s ={nt|t = (i MOD 2s + 2s−1 + j) MOD 2s−1+a+
(i DIV 2s) ∗ 2s + b ∗ 2s−1; j = 0, 1, ..., 2s−1 − 1} ,
onde
a =
1 se MOD 2s < 2s−1
0 outros casos
b =
1 se a = 1 AND (i MOD 2s + 2s−1 + j)
MOD 2s−1+a + (i DIV 2s) ∗ 2s < i
0 outros casos
Quando um nodo i realiza testes em nodos pertencentes a Ci,s, ele executa testes sequen-
cialmente ate encontrar um nodo sem-falhas, ou ate descobrir que todos os outros nodos
3.3 O Algoritmo Hi-ADSD 36
estao falhos. Pela funcao Ci,s quando dois nodos diferentes testam nodos de um cluster eles
iniciam testando nodos diferentes. A tabela 1 mostra a funcao Ci,s para um sistema com 8
nodos.
Tabela 1: Ci,s para um sistema com 8 nodos.
s C0,s C1,s C2,s C3,s C4,s C5,s C6,s C7,s
1 1 0 3 2 5 4 7 62 2, 3 3, 2 0, 1 1, 0 6, 7 7, 6 4, 5 5, 43 4, 5, 6, 7 5, 6, 7, 4 6, 7, 4, 5 7, 4, 5, 6 0, 1, 2, 3 1, 2, 3, 0 2, 3, 0, 1 3, 0, 1, 2
Quando um nodo sem-falhas e testado ele fornece informacoes sobre todos os nodos da
Ci,s ao qual ele pertence. Se nenhum nodo sem-falhas e encontrado em uma determinada
Ci,s o nodo i passa a testar Ci,s+1 no mesmo intervalo de testes, ate encontrar um nodo
livre de falhas, ou descobrir que todos os nodos estao falhos. A figura 4 mostra os clusters
testados pelo nodo 0. Inicialmente o nodo 0 testa o nodo 1 do cluster de tamanho 1, na
proxima rodada de testes testa o cluster de tamanho 2 composto pelos nodos 2 e 3, por fim
testa o cluster de tamanho 4 que contem os nodos 4, 5, 6 e 7 e entao retorna para testar o
cluster de tamanho 0.
0 1
2 3
4 5 6 7
Figura 4: Clusters testados pelo nodo 0 executando o algoritmo Hi-ADSD.
O algoritmo realiza testes de forma assıncrona, isto significa que em uma mesma ro-
dada os nodos podem estar testando clusters de tamanhos diferentes. A latencia pode
chegar a, no maximo, (log2N)2 rodadas de testes. Simulacoes (DUARTE Jr.; NANYA, 1998)
demonstraram que a latencia em geral e menor que (log2N)2, e que se os nodos estiverem
realizando os testes de forma sincronizada a latencia e da ordem de log2N rodadas de teste.
3.4 O Algoritmo Hi-ADSD with Detours 37
No algoritmo Hi-ADSD existe uma situacao de falhas em que pode ser executados N2/4
testes em uma unica rodada. Suponha que exista um cluster com tamanho N/2 onde todos
os nodos estao falhos e que os N/2 nodos restantes e sem-falhas realizem testes sobre este
cluster falho. Entao teremos N/2 nodos realizando N/2 cada, resultando em um total de
N2/4 testes. Portanto, neste pior caso o numero de testes executados em uma rodada pode
ser da ordem O(N2), que e a mesma ordem de complexidade de algoritmos de forca bruta.
3.4 O Algoritmo Hi-ADSD with Detours
Com o objetivo de diminuir o numero maximo de testes realizados no algoritmo Hi-
ADSD surgiu o algoritmo Hi-ADSD with Detours (DUARTE Jr.; BRAWERMAN; ALBINI,
1998). O objetivo e cumprido por meio de uma mudanca na estrategia de testes. O
resultado e que a cada log2N rodadas sao executados no maximo Nlog2N testes. Os clus-
ters sao organizados da mesma maneira que no algoritmo Hi-ADSD e a latencia tambem e
mantida.
No algoritmo Hi-ADSD with Detours, quando o nodo testa um nodo falho de um de-
terminado cluster ele nao continua a testar os demais nodos deste cluster. Nesta situacao o
cluster e dito bloqueado e o nodo testador procura obter informacoes sobre os nodos deste
cluster ao testar outros clusters. As informacoes podem ser obtidas por caminhos alter-
nativos no grafo de testes. Estes caminhos alternativos sao chamados de detours. Testes
extras sao realizados nos nodos do cluster bloqueado para os quais nao foram encontrados
detours.
Os nodos do algoritmo Hi-ADSD with Detours sao organizados em clusters da mesma
forma que no algoritmo Hi-ADSD. A definicao de Ci,s tambem e a mesma adotada no
Hi-ADSD original, apresentada na secao anterior.
Uma rodada de testes e definida como o perıodo de tempo no qual todos os nodos sem-
falhas testam um cluster. A latencia do algoritmo e definida como o numero de rodadas
3.4 O Algoritmo Hi-ADSD with Detours 38
de testes necessarias para que todos os nodos sem-falha do sistema realizem o diagnostico
de um evento. Considera-se que durante o diagnostico de um evento um novo evento nao
ocorre no sistema.
O grafo de testes livres de falhas do sistema, T (S), e um grafo onde os vertices sao os
nodos do sistema e uma aresta direcionada entre o nodo i e j indica que o nodo i testou
o nodo j como sem-falhas no ultimo intervalo de teste. Quando todos os nodos estao
sem-falhas T (S) e um hipercubo.
A distancia de diagnostico entre o nodo i e o nodo p, di,p, e a menor distancia entre
os nodos i e p em T (S). Por exemplo, na figura 5, podemos verificar que d0,5 = 2, ou
seja a distancia de diagnostico do nodo 0 ate o nodo 5 e 2. Ainda, define-se Di,k como
sendo o conjunto de todos os nodos p tal que di,p ≤ k. Assim de acordo com a figura 5,
D0,1 = {1, 2, 4}, D0,2 = {1, 2, 4, 3, 5, 6} e D0,3 = {1, 2, 4, 3, 5, 6, 7}.
2
5
41
3 6
7
0
Figura 5: O grafo T (S) para um sistema com 8 nodos.
Ri,s,p e a lista ordenada de nodos que podem ser alcancadas pelo nodo i a partir do
nodo p com distancia de diagnostico menor ou igual a s e menor que a distancia do nodo
i quando todos os nodos estao sem-falhas. Ri,s,p e dada pela expressao abaixo. A figura 5
mostra R0,3,2 = {6, 7}.
Ri,s,p = (Ci,s ∩ Dp,s−1) − Di,di,p
Um detour do nodo i ao nodo j e um caminho em T (S) do nodo i ao nodo j passando
3.4 O Algoritmo Hi-ADSD with Detours 39
por nodos fora do cluster ao qual o nodo j pertence. O detour deve ter exatamente o mesmo
numero de arestas do caminho mais curto entre i e j no caminho que contem apenas nodos
do cluster ao qual j pertence.
A figura 6 mostra um sistema com 8 nodos executando o algoritmo Hi-ADSD with
Detours, os nodos assinalados estao falhos. As linhas pontilhadas mostram os testes que
seriam executados pelo Hi-ADSD sem detours para diagnosticar os nodos 5, 6 e 7. No Hi-
ADSD with Detours a informacao do nodo 5 e obtida atraves do nodo 1, e as informacoes
sobre os nodos 6 e 7 sao obtidas atraves do nodo 2.
0 1
7632
4 5
Figura 6: Sistema executando o algoritmo Hi-ADSD with Detours.
A especificacao do algoritmo e feita utilizando as funcoes more-info e more-tests. O
testador executa more-info depois de testar um nodo sem-falhas para determinar se e ne-
cessario obter informacoes adicionais pelo nodo testado. A funcao e dada abaixo, onde:
nodo i e o testador; nodo p e o nodo sem-falhas testado em Ci,s′ ; a lista Ri,log2N,p contem
todos os nodos cujas informacoes podem ser obtidas pelo nodo i atraves do nodo p; e o
conjunto Bi,s contem os nodos bloqueados de um dado Ci,s. Quando o nodo testado em
um dado cluster esta falho e o testador nao obtem informacoes sobre os outros nodos do
cluster, estes nodos sao chamados de bloqueados.
more-info(i, p) = Ri,log2N,p ∩ Bi,s, s′ < s <= log2N
A funcao more-tests e executada quando um nodo falho e testado, para determinar se
3.4 O Algoritmo Hi-ADSD with Detours 40
e necessario executar testes adicionais no mesmo cluster, ou seja, se nao existem detours
para os nodos bloqueados. A funcao more-tests e dada pela formula abaixo, onde o nodo i
e o testador, o nodo p e o nodo testado falho, Ci,s,p a lista contendo todos nodos sobre os
quais o nodo p pode dar informacao para o nodo i e s varia de acordo com o Ci,s ao qual p
pertence:
more-testes(i, s) = Bi,s − Ri,s,p|p ∈ Ci,s′ e 1 <= s′ < s
O pseudo codigo e apresentado na figura 7.
ALGORITHM Hi−ADSD with Detours { at node i }i n i t i a l i z e a l l s e t s Bi , s empty ;REPEAT FOREVER
FOR s = 1 to LogN DOp := f i r s t node in Ci , st e s t (p)IF p i s f au l t−f r e e THEN
get Ci , s d i a gno s i s in fo rmat ion ;update Bi , s ;get more in fo ( i , p ) d i a gno s i s in fo rmat ion ;update Bi , s ;
ELSE p i s f a u l t y THENBi , s = Ci , s − pWHILE more−t e s t s ( i , s ) i s not empty DO
k = f i r s t node in more t e s t s ( i , s )t e s t ( k ) ; Bi , s = Bi , s − k ;IF k i s f au l t−f r e e THEN
get Bi , s d i a gno s i s in fo rmat ion ; update Bi , s ;get more in fo ( i , k ) d i a gno s i s in fo rmat ion ; update Bi , s ;
END IFEND WHILE
END IFEND FOR
END REPEAT
Figura 7: Especificacao do algoritmo Hi-ADSD with Detours.
Simulacoes mostram que o Hi-ADSD with Detours (DUARTE Jr.; BRAWERMAN; ALBINI,
1998) precisa de um numero menor de testes em relacao ao Hi-ADSD original em diversas
situacoes de falhas. Na tabela 2 estao os resultados da simulacao de um sistema com
64 nodos. Os resultados mostram que o emprego de detours diminui o numero de testes
necessarios para completar o diagnostico do sistema.
3.5 O Algoritmo Hi-ADSD with Timestamps 41
Tabela 2: Simulacoes de um sistema com 64 nodos executando os algoritmos Hi-ADSD eHi-ADSD com detours
Situacao de Falha Hi-ADSD Hi-ADSD with Detours
32 nodos falhos de 383 285forma aleatoriaPior caso do Hi-ADSD 1184 191Pior caso do Hi-ADSD 384 384with Detours
3.5 O Algoritmo Hi-ADSD with Timestamps
Eventos sao definidos como a mudanca de estado de um nodo detectada pelo algoritmo
de diagnostico. Um evento ocorre quando um nodo falho se torna sem-falhas ou quando
um nodo sem-falhas se torna falho. Os algoritmos hierarquicos baseados no modelo PMC
assumem situacoes de falhas estaticas, nao podendo haver um novo evento enquanto todos
os nodos sem-falhas do sistema nao detectarem o evento anterior. Esta assercao e artificial
e pode nao ser garantida facilmente em um sistema real.
O algoritmo Hi-ADSD with Timestamps (DUARTE Jr.; ALBINI; BRAWERMAN, 2000) e
um algoritmo baseado no algoritmo Hi-ADSD with Detours e trabalha com falhas dinamicas,
onde eventos podem ocorrer antes do diagnostico do evento anterior ter sido completado
por todos os nodos. O timestamp e uma informacao guardada sobre o estado de cada
nodo do sistema, a informacao e um contador incrementado a cada mudanca de estado
(RANGARAJAN; DAHBURA; ZIEGLER, 1995; DUARTE Jr. et al., 1997). A utilidade do times-
tamp e permitir datar informacoes, distinguindo as informacoes mais atualizadas das menos
atualizadas.
Ao testar um nodo sem-falhas em um cluster, no algoritmo Hi-ADSD with Timestamps,
nao sao obtidas somente informacoes sobre o cluster do nodo testado e possıveis detours.
Sempre que um nodo i testa um nodo j como sem-falhas sao lidas informacoes de diagnostico
de todos os nodos que estao a uma distancia de diagnostico de ate log2N − 1 do nodo i
passando pelo nodo j, um conjunto que tem sempre N/2 nodos. Como as informacoes
3.5 O Algoritmo Hi-ADSD with Timestamps 42
sobre um determinado nodo podem ser obtidas a partir de varios nodos testados, entao
emprega-se o timestamp para selecionar a informacao de diagnostico mais recente.
A latencia media do algoritmo Hi-ADSD with Timestamps e reduzida em relacao ao
algoritmo Hi-ADSD with Detours. O numero maximo de testes e o mesmo do Hi-ADSD
with Detours ja que a estrategia de testes e a mesma. Simulacoes feitas em sistemas
de 512 nodos mostram que o algoritmo Hi-ADSD with Timestamps (DUARTE Jr.; ALBINI;
BRAWERMAN, 2000) e em media quatro vezes mais rapido para completar o diagnostico de
uma falha que o Hi-ADSD with Detours. Para este sistema de 512 nodos o Hi-ADSD with
Detours teve uma latencia de 40 rodadas de teste, enquanto no Hi-ADSD with Timestamps
a latencia foi de 12 rodadas.
3.5.1 Diagnostico Dinamico de Eventos
Uma das melhorias do Hi-ADSD with Timestamps em relacao aos outros algoritmos
hierarquicos e a capacidade de diagnosticar certos eventos dinamicos, ou seja, eventos
que ocorrem antes do diagnostico do evento anterior por todos os nodos sem-falha. O
modelo de falhas estatico, adotado pelos demais algoritmos hierarquicos de diagnostico
apresentados, considera que um novo evento nao ocorre antes que todos os nodos sem-falhas
tenham diagnosticado o evento anterior. O modelo estatico considera que o algoritmo de
diagnostico esta analisando uma imagem retirada do sistema em um determinado intervalo
de tempo (BLOUGH; BROWN, 1999). O modelo estatico entretanto nao e adequado para
um ambiente real, uma vez que falhas podem ocorrer durante a execucao do algoritmo de
diagnostico. Considerando-se um modelo de falhas dinamico e necessaria a especificacao
de um procedimento de recuperacao para os nodos que sao reparados durante a execucao
do algoritmo.
Quando um nodo falho e reparado, ele nao tem informacoes de diagnostico sobre o sis-
tema. A medida em que o nodo comeca a executar testes e obter informacoes de diagnostico
de outros nodos sem-falhas ele atualiza sua informacao de diagnostico. E necessario distin-
3.5 O Algoritmo Hi-ADSD with Timestamps 43
guir informacoes de diagnostico atualizadas e nao atualizadas. Caso contrario a informacao
incorreta, nao atualizada, pode ser propagada pelo sistema.
Considere que as informacoes de diagnostico que cada nodo mantem sobre os nodos
do sistema sao organizadas em uma tabela, onde cada linha corresponde a um nodo. Um
campo chamado u-bit pode ser inserido em cada linha e utilizado para indicar se a in-
formacao de diagnostico foi ou nao atualizada desde a inicializacao do nodo. Este campo
pode ser implementado como um bit, cujo valor 1 indica que informacao e atualizada e 0
em outro caso.
Ao reparar-se de uma falha o nodo atribui a todos os seus u-bits o valor 0. Ao encon-
trar um nodo sem-falhas que ja tenha completado o processo de inicializacao ele obtem
informacoes de todos os nodos do sistema. Caso um testador se recupere e teste todos os
nodos como falhos (ou nao encontre nenhum nodo sem-falhas atualizado) entao ele pre-
cisa atribuir todos u-bits para 1. Durante a inicializacao do algoritmo ocorre algo similar,
pois apesar de encontrar nodos sem-falhas estes nodos ainda nao possuem informacao de
diagnostico atualizadas, ou seja, tem o u-bit igual a 0.
3.5.2 Especificacao do Algoritmo
Considere um sistema S composto de N nodos, que podem estar falhos ou sem-falhas.
Assuma que o sistema e totalmente conectado, ou seja, existe um enlace de comunicacao
entre qualquer par de nodos, e os enlaces nao falham. Neste sistema os nodos sem-falhas
sao capazes de testar e comunicar os resultados de forma confiavel.
O intervalo de testes e definido como o perıodo de tempo no qual um nodo sem-falhas
testa um cluster. O grafo de testes livres de falhas do sistema, T (S), e um grafo direcionado
cujos vertices representam os nodos do sistema e uma aresta direcionada entre o nodo i e j
indica que o nodo i testou o nodo j como sem-falhas no ultimo intervalo de teste. Quando
todos os nodos estao sem-falhas T (S) e um hipercubo. A distancia de diagnostico entre o
3.5 O Algoritmo Hi-ADSD with Timestamps 44
nodo i e o nodo p, di,p, e a menor distancia entre os nodos i e p em T (S).
O grafo de testes livres de falhas de i, TFFi, e um grafo direcionado cujos vertices sao
os nodos de S. Existe a aresta direcionada de a para b, ab, em TFFi se ab pertence a T (S)
e di,a < di,b. A figura 8 mostra TFF0 para um sistema com 8 nodos.
2
5
41
3 6
7
0
Figura 8: O grafo TFF0 para um sistema com 8 nodos.
Ci,s,p e definido como a lista ordenada de nodos que podem ser alcancados pelo nodo i
a partir do nodo p com uma distancia de diagnostico menor ou igual a s − 1. A figura 9
mostra C0,3,2. A funcao Ci,s,p corresponde ao cluster testado quando o nodo i e o testador.
2
5
41
3 6
7
0
Figura 9: Um exemplo de Ci,s,p: C0,3,2.
A estrategia de testes do algoritmo Hi-ADSD with Timestamps e a mesma utilizada pelo
algoritmo Hi-ADSD with Detours. A cada intervalo de testes um nodo testa um cluster.
Apos log2N intervalos de testes o primeiro cluster e testado novamente. A figura 10 mostra
3.5 O Algoritmo Hi-ADSD with Timestamps 45
os clusters testados pelo nodo 0. Quando o nodo 0 testa o nodo 1 obtem informacoes sobre
os nodos do cluster C0,3,1, ou seja, nodo 1, nodo 3, nodo 5 e nodo 7. Os outros dois clusters
testados, C0,3,2 e C0,3,4, sao analogos.
0
2
5
41
3 6
7
Figura 10: Clusters testados pelo nodo 0.
No algoritmo Hi-ADSD with Timestamps sempre que um nodo sem-falhas e testado
sao obtidas informacoes do conjunto de nodos com distancia de no maximo log2N − 1, ou
seja, sobre N/2 nodos. No Hi-ADSD with Detours o tamanho do conjunto de informacoes
obtidas e limitado pelo tamanho do cluster testado mais os nodos retornados pela funcao
more-info.
A limitacao do conjunto de informacoes obtidas no detours e necessaria porque no
algoritmo Hi-ADSD with Detours um nodo i nao pode obter informacoes de diagnostico
sobre um nodo j de dois ou mais nodos. No Hi-ADSD with Timestamps o nodo i pode obter
informacoes sobre um nodo j de dois ou mais nodos sem-falhas. Neste caso e necessario
determinar qual informacao sobre o estado de j e mais recente. Por exemplo, na figura 10,
e possıvel verificar que o nodo 0 pode obter informacoes sobre o nodo 5 pelos clusters C0,3,1
e C0,3,4.
O timestamp e um mecanismo que permite datar a informacao de diagnostico e e im-
plementado com um contador das mudancas de estado. Cada vez que um teste e executado
e o testador descobre que o nodo testado mudou de estado o contador e incrementado.
3.5 O Algoritmo Hi-ADSD with Timestamps 46
Para garantir que o nodo i mantenha as informacoes mais recentes sobre nodo j ele
precisa comparar o timestamp do estado de j obtido com o seu timestamp local. Se o
timestamp do estado de j obtido e menor que o timestamp de j local entao a informacao de
diagnostico e desatualizada e i nao deve atualizar o estado de j. Caso contrario, o timestamp
local de j for menor do que o obtido a informacao e mais nova, entao o timestamp local e
a informacao de diagnostico devem ser atualizadas.
Se o primeiro nodo testado de Ci, s, p estiver falho, o testador tentara encontrar detours
para os nodos destes clustres atraves de outros nodos sem-falhas testados. Um teste extra
somente e executado em cluster se nao forem encontrados detours.
47
4 Diagnostico Distribuıdo Baseado
no Algoritmo DiVHA
Este capıtulo apresenta um novo algoritmo de diagnostico distribuıdo, hierarquico e
adaptativo baseado no Distributed Virtual Hypercube Algorithm (DiVHA). Dado um con-
junto de nodos e seus estados, o algoritmo DiVHA determina um grafo de testes com uma
topologia baseada no hipercubo. Quando todos os nodos estao sem-falha o grafo e um
hipercubo completo. Na presenca de nodos falhos, a topologia deixa de ser um hipercubo
completo, e testes sao adicionados de forma a preservar duas proprieadades do hipercubo:
o diametro logarıtmico, ou seja, a distancia entre qualquer par de nodos i e j no grafo de
testes nunca e maior que log2N ; e o numero maximo de arestas Nlog2N .
O algoritmo de diagnostico utiliza o algoritmo DiVHA para atribuir os testes e deter-
minar o fluxo de informacao no sistema. Tirando proveito das caracterstıcas do grafo do
DiVHA, o novo algoritmo de diagnostico permite que todos os nodos sem-falha determinem
o estado de todos outros nos do sistema em no maximo log2N rodadas de testes, reque-
rendo no maximo N ∗ (log2N)2 testes. De nosso conhecimento, nenhum outro algoritmo
distribuıdo de monitoracao apresenta um numero tao baixo de mensagens.
O restante deste capıtulo esta organizando da seguinte maneira. A secao 4.1 apresenta
o modelo do sistema. O algoritmo de diagnostico e especificado na secao 4.2, na sequencia
a secao 4.3 apresentada a especificacao do algoritmo DiVHA. A prova de correcao dos
algoritmos propostos e apresentada na secao 4.4. Finalmente a secao 4.5 traz resultados
obtidos da simulacao do novo algoritmo de diagnostico.
4.1 Modelo do Sistema 48
4.1 Modelo do Sistema
Considere um sistema S composto por um conjunto de N nodos, n0, n1,...,nN−1. Al-
ternativamente nos referimos ao nodo ni como nodo i. O sistema e considerado totalmente
conectado, ou seja, qualquer par de nodos pode se comunicar diretamente. Assumimos
tambem um sistema sıncrono onde os relogios nao estao sincronizados.
Um nodo ni pode assumir um de dois estados, sem-falha ou falho. Um evento e definido
como a mudanca de estado de um nodo, tanto de sem-falha para falho como de falho para
sem-falha. A colecao dos estados de todos os nodos e o estado do sistema. Se considera
tambem um modelo dinamico para os estados do sistema, ou seja, os nodos podem alternar
continuamente entre o estado falho e o estado sem-falha.
Um nodo no estado sem-falha e considerado como capaz de testar outros nodos e infor-
mar corretamente os resultados destes testes. Um teste consiste em uma tarefa atribuıda
pelo nodo testador ao nodo testado. A tarefa e executada e o resultado devolvido para o
testador que compara o resultado com o esperado. Isto significa que o diagnostico traba-
lha com uma classe de falhas melhor caracterizada como falha de computacao, que ocorre
quando um processo falha em produzir a resposta esperada para uma dada entrada. Os
testes sao realizados periodicamente, dentro de um intervalo de testes fixo, que pode variar
dependendo da tecnologia do sistema, de alguns poucos nanosegundos a varios minutos.
Uma rodada de testes e definida como o perıodo de tempo em que todos os nodos no
estado sem-falha executam seus testes. A latencia do sistema e definida como o tempo
necessario para que todos nodos no estado sem-falha descubram a ocorrencia de um novo
evento.
4.2 Especificacao do Algoritmo de Diagnostico Distribuıdo 49
4.2 Especificacao do Algoritmo de Diagnostico Dis-
tribuıdo
Seja o grafo de testes, tambem chamado T (S), um grafo direcionado cujos nodos sao
os nodos de S. Existe uma aresta direcionada do nodo i para o nodo j se o nodo i testa o
nodo j na rodada de testes mais recente. Assim T (S) representa todos os testes executados
na ultima rodada de testes. Quando todos os nodos estao no estado sem-falha, T (S) e um
hipercubo. Quando alguns nodos sao considerados falhos, T (S) deixa de ser um hipercubo e
novas arestas sao adicionadas com o objetivo de preservar duas propriedades do hipercubo:
(1) o diametro logarıtmico, ou seja, a distancia entre qualquer par de nodos i e j em T (S)
nunca e maior que log2N ; e (2) o numero total de arestas em T (S) nunca e maior que
Nlog2N .
O algoritmo mostrado na figura 11 e executado por todos os nodos para determinar e
obter informacoes sobre o estado dos outros nodos do sistema, com o objetivo de manter o
hipercubo. A cada rodada de testes todos nodos no estado sem-falha executam seus testes,
o conjunto de testes atribuıdos ao nodo i chamado t(i) e o conjunto de nodos adjacentes
ao nodo i em T (S). Seja a distancia do nodo i para o nodo j, chamada di,j ou d(i, j), o
tamanho do caminho com menor numero de arestas do nodo i para o nodo j em T (S). Seja
Di,k o conjunto de todos os nodos p tal que di,p ≤ k.
Quando o nodo i testa um nodo j no estado sem-falha ele obtem informacao sobre
todos os nodos k com distancia de j menor ou igual a log2N − 1, ou seja k ∈ Dj,log2N−1, tal
que dj,k < di,k. Quando todos os nodos em T (S) estao no estado sem-falha, em um unico
teste o testador obtem informacoes de estado de sobre N/2 nodos. Ao executar todos seus
testes o nodo i obtem informacoes sobre o estado de todos os nodos do sistema.
E possıvel que um nodo i obtenha informacao sobre um nodo k atraves de um ou mais
nodos. Para garantir que o nodo i obtenha apenas a informacao mais nova de estado do
nodo k utilizamos o mecanismo de timestamps. Esta estrategia permite datar a informacao
4.3 O Algoritmo DiVHA 50
Dis t r ibuted Diagnos i s with DiVHAT(S)=DiVHA(S)DO
FOR EACH j IN t ( i )t e s t ( j )IF the s t a t e o f t e s t ed node has changed THEN
update s t a tu s and timestamp in format ion about jIF node j i s f au l t−f r e e THEN
get from j in fo rmat ion aboutnodes k in Dk, logN−1 such that d( j , k ) < d( i , k )
update l o c a l in fo rmat ion comparing timestampsIF new events have been d i s cove r ed THEN
update T(S) with DiVHAEND FORSLEEP un t i l the next Test ing I n t e r v a l
FOREVER
Figura 11: Diagnostico distribuıdo baseado no algoritmo DiVHA.
de estado, ou seja, e possıvel determinar se uma informacao recebida e mais nova que
outra tambem recebida ou ja mantida. O timestamp e implementado como um contador
das mudancas de estados, em outras palavras o timestamp e incrementado sempre que um
teste e executado e o testador descobre que o estado no nodo testado foi alterado. Quando
um nodo detecta um evento, ele executa o algoritmo DiVHA, apresentado abaixo, que
determina o novo conjunto de testes que devem ser executados pelo nodo.
4.3 O Algoritmo DiVHA
Os nodos do sistema executam o algoritmo DiVHA (Distributed Virtual Hypercube
Algorithm) com o objetivo de determinar o conjunto de testes a ser executado dado o
estado percebido do sistema. A especificacao do DiVHA e dada na figura 12.
Inicialmente o grafo T (S) tem apenas vertices, correspondentes aos nodos do sistema,
e nenhuma aresta. Os nodos sao organizados de forma hierarquica para calcular as arestas.
Clusters sao utilizados para agrupar nodos, que sao conjuntos de nodos cujo tamanho cresce
progressivamente em potencias de 2. Um cluster de p nodos nj, ..., nj+p−1, onde p e uma
potencia de 2 e e maior que 1, e formado pela uniao de dois clusters, um contendo os
nodos nj, ..., nj+p/2−1 e outro nj+1, ..., nj+p−1. A figura 13 mostra um sistema de 8 nodos
4.3 O Algoritmo DiVHA 51
DiVHA( system S)T(S) i n i t i a l l y does not have any edgeFOR s=1 to logN do
FOR d i s t ance=1 to s doFOR each f a u l t f r e e node i =0 . . .N−1 do
FOR each node j that be longs c ( i , s ) such that h( i , j ) = d i s t anceIF (d( i , j ) > s or non ex i s t en t ) THEN
add edge ( i , j ) to T( s )next i
UNTIL d( i , j ) <= s , such that node i i s f au l t−f r e eand node j be longs to c ( i , s )
Figura 12: Especificacao do algoritmo DiVHA.
organizado em clusters. Um cluster Ci,s pode ser definido recursivamente pela expressao:
Ci,s = Cj,s−1 ∪ Ci,s−1, j = i ⊕ 2s−1 e
Ci,1 = j, j = i ⊕ 1
O algoritmo considera os clusters do menor para o maior, ou seja, o tamanho do cluster e
incrementado com s variando de 1 ate log2N . A cada iteracao o algoritmo computa arestas
de nodos sem-falha i, variando i indo de 0 ate N − 1, para nodos pertencentes a Ci, s.
Desta forma sao adicionadas arestas entre o nodo 0 e nodos pertencentes ao cluster C0,s,
entre o nodo 1 e os nodos pertencentes ao cluster C1,s, e assim por diante ate o nodo N − 1
e os nodos pertencentes ao cluster CN−1,s. Uma aresta e adicionada entre o nodo i e o
nodo j ∈ Ci, s sempre que nao existir um caminho do nodo i para o nodo j em T (S) com
distancia ≤ s. Uma iteracao termina quando existe pelo menos um caminho com tamanho
≤ s entre todo nodo i no estado sem-falha e os nodos pertencentes a Ci, s.
0 1
7632
4 5
Figura 13: Sistema de 8 nodos agrupados em clusters pelo algoritmo DiVHA.
A adicao de arestas e feita de forma distribuıda entre os nodos do sistema baseando-se
4.4 Provas Formais 52
nas distancias do hipercubo. A distancia no hipercubo do nodo i para o nodo j, chamada
hi,s ou h(i, j), e o numero de arestas no caminho mais curto entre o nodo i e o nodo
j em um hipercubo perfeito. Esta estrategia para adicao de arestas permite formar um
hipercubo quando todos os nodos estao no estado sem-falha e distribuir entre os nodos de
forma balanceada as arestas adicionais que podem ser necessarias quando existem nodos
considerados falhos.
4.4 Provas Formais
Nesta secao sao apresentadas as provas formais que o DiVHA garante o diametro lo-
garıtmico do sistema mesmo quando o numero de nodos no estado sem falha nao e potencia
de 2, e que o numero total de arestas em T (S) nao e maior que Nlog2N . Tambem provamos
que a latencia para deteccao de eventos e log2N no pior caso.
Teorema 1. No grafo T (S) determinado pelo algoritmo DiVHA, a distancia de qualquer
nodo sem-falha para qualquer outro nodo e ≤ log2N .
Demonstracao. Considere o algoritmo da figura 12, o laco mais externo a cada iteracao
insere arestas que garantem d(i, j) ≤ s para todo ni sem-falha ∈ S e nj ∈ Ci,s. Vamos
provar por inducao que ao termino de cada iteracao s temos d(na, nb) ≤ s para todo
na, nb ∈ Ci,s+1. Dado que Ci,log2N+1 = S, ao final da ultima iteracao a distancia de qualquer
nodo sem-falha para outro nodo e menor ou igual a log2N .
Base. Na iteracao em que s = 1, d(na, nb) = 1 para todo na sem-falha, nb ∈ Ci,2.
Na primeira iteracao sao inseridas arestas garantindo d(ni, nj) ≤ 1 para todo ni sem-
falha ∈ S e nj ∈ Ci,s. Por definicao Ci,2 = Ci,1∪Cj,1, i = k⊕1, ou ainda, Ci,2 = Ci,1 ∪{ni}.
Suponha na sem-falha, nb ∈ Ci,2. Entao nb ∈ Ca,1 e logo d(na, nb) = 1, ja que d(i, j) ≤ s
para todo ni sem-falha ∈ S e nj ∈ Ci,s.
4.4 Provas Formais 53
Hipotese de Inducao. Na iteracao s, d(na, nb) ≤ s para todo na sem-falha, nb ∈ Ci,s+1.
Passo. Ao final da iteracao s+1 a d(na, nb) ≤ s+1 para todo na sem-falha, nb ∈ Ci,s+2.
Na iteracao s+1 sao inseridas arestas garantindo d(ni, nj) ≤ s+1 de todo ni sem-falha
∈ S para todo nj ∈ Ci,s+1. Ci,s+2 e dado por Ci,s+1 ∪ Cj,s+1, j = i ⊕ 2s. Suponha na sem-
falha e nb ∈ Ci,s+2. Se na, nb pertencem ao mesmo cluster s + 1 pela hipotese de inducao,
d(na, nb) ≤ s; se na e nb pertencem a clusters s+1 distintos, entao na ∈ Cb,s+1 e nb ∈ Ca,s+1.
Logo d(na, nb) ≤ s + 1 porque nb ∈ Ca,s+1 e d(ni, nj) ≤ s + 1 para todo ni sem-falha e todo
nj ∈ Ci,s+1. Portanto d(na, nb) ≤ s + 1 para todo na sem-falha, nb ∈ Ci,s+2.
Teorema 2. No grafo T (S) determinado pelo algoritmo DiVHA, o numero maximo de ares-
tas e Nlog2N .
Demonstracao. Considere o algoritmo da figura 12, a cada iteracao s sao adicionadas ares-
tas entre clusters Ci,s e Cj,s distintos formando Ci,s+1. Suponha que uma aresta e adicionada
do nodo nk ∈ Ci,s para o nodo nl ∈ Cj,s, como mostra a figura 14. Da demonstracao indu-
tiva do teorema 1, d(ni, nk) ≤ s − 1 para todo ni sem-falha ∈ Ci,s, com a aresta inserida
aresta ij → jk, temos d(ni, nl) ≤ s para todo ni sem-falha ∈ Ci,s. Assim o DiVHA nao
insere nenhuma outra aresta para nl nesta iteracao, ou seja, um nodo recebe no maximo
uma aresta por iteracao; como o numero total de iteracoes e log2N , cada nodo em T (S)
recebe no maximo log2N arestas, e T (S) tem no maximo Nlog2N arestas.
Teorema 3. Uma alteracao percebida no estado de um nodo demora no maximo log2N
rodadas de testes para ser propagada para todos os nodos no estado sem-falha.
Demonstracao. Suponha que um evento ocorra no nodo e. Vamos demonstrar por inducao
que todo nodo no estado sem-falha a distancia d do nodo e descobre o evento em no maximo
d rodadas de testes. Como a distancia maxima no grafo T (S) dado pelo DiVHA e log2N ,
a inducao e suficiente para provar o teorema.
4.4 Provas Formais 54
Figura 14: Aresta adicionada do nodo nk ∈ Ci,s para o nodo nl ∈ Cj,s.
Base: Todo nodo ni sem-falha tal que d(ni, ne) = 1 descobre o evento em ne em no
maximo uma rodada de testes. Trivial, todo os nodo sem-falha testa todos nodos a distancia
1 a cada rodada de testes.
Hipotese de Inducao: Todo nodo ni sem-falha tal que d(ni, ne) = d descobre o evento
em ne em no maximo d rodadas de testes.
Passo: Todo nodo ni sem-falha tal que d(ni, ne) = d + 1 descobre o evento em ne em
no maximo d + 1 rodadas de testes.
Considere nj tal que d(nj, ne) < d+1, existe portanto um caminho {nj = n0, ..., nd+1 =
ne} com d + 1 arestas entre o nodo nj e o nodo ne. O caminho {n1, ..., nd+1 = ne} tem d
arestas, logo n1 esta a distancia d do nodo e e pela hipotese de inducao descobre o evento
em no maximo d rodadas de testes. Como nj e adjacente a n1 e testa n1 em no maximo uma
rodada de testes, dado que d(n1, ne) ≤ log2N e d(n1, e) < d(nj, e), nj obtem informacao
sobre o novo estado do nodo ne ao testar n1. Logo, nj descobre o evento em ne em no
maximo d + 1 rodadas de testes.
4.5 Resultados de Simulacao 55
4.5 Resultados de Simulacao
Nesta secao sao apresentados resultados obtidos da simulacao do novo algoritmo de di-
agnostico baseado no algoritmo DiVHA. A simulacao foi conduzida utilizando a linguagem
de simulacao de eventos discretos SMPL (Simple Portable Simulation Language) (MAC-
DOUGALL, 1987). Os nodos foram modelados como estrutras do SMPL, cada nodo foi
identificado com um numero de token SMPL. Foram conduzidas tres series de experimen-
tos. A primeira serie de experimentos mostra o numero de testes necessarios como funcao
do numero de nodos falhos. A segunda serie de experimentados apresentados mostra a
latencia do algoritmo para uma serie de situacoes de falhas geradas aleatoriamente. Fi-
nalmente, a terceira serie de experimentos compara o novo algoritmo com algorimos de
diagnostico distribuıdos e hierarquicos publicados anteriormente.
4.5.1 Numero de Testes Necessarios
O proposito destes experimento e medir o numero de testes necessarios em um sistema
executando o algoritmo de diagnostico baseado no DiVHA. Foram simulados sistemas com
64, 128 e 256 nodos, sendo geradas cerca de 5 milhoes de situacoes de falhas diferentes. Para
cada situacao de falha DiVHA foi executado e o grafo de testes do sistemas construıdo. O
grafo de teste determina o numero de testes executados no sistema, dado que cada aresta
no grafo representa um teste a ser realizado.
O grafo apresentado na figura 15 apresenta os resultados obtidos por simulacao para
um sistema com 64 nodos. O eixo X representa o numero de nodos falhos na situacao de
falha. O eixo Y apresenta o melhor caso e o pior caso do numero de testes executados para
as situacoes de falhas simuladas. O melhor caso corresponde a situacao de falhas que requer
o menor numero de testes, o pior caso corresponde a situacao de falhas que requer o maior
numero de testes. Estes resultados mostram que o numero de testes diminui conforme o
numero de nodos falhos aumenta. Assim, o pior caso para o numero de testes corresponde
4.5 Resultados de Simulacao 56
a situacao de falhas em que todos os nodos estao sem-falha.
0
24
48
72
96
120
144
168
192
216
240
264
288
312
336
360
384
63 60 56 52 48 44 40 36 32 28 24 20 16 12 8 4 0
# te
stes
# nodos no estado falho
pior casomelhor caso
Figura 15: Numero de testes necessarios para um sistema com 64 nodos.
Com o objetivo de verificar a escalabilidade do algoritmo o experimento anterior foi
repetido para sistemas com 128 e 256 nodos. O grafo na figura 16 mostra o resultado para
um sistema com 128 nodos. O grafo na figura 17 mostra o resultado para um sistema com
256 nodos. Comparando os resultados obtidos para sistemas com 64, 128 e 256 nodos, po-
demos concluir que o algoritmo apresenta um comportamente muito similar para diferentes
tamanhos de sistema. O fato de que o pior caso para o numero de testes e logarıtmico, ou
seja, no maximo Nlog2N testes sao executados em uma dada rodada de testes, tambem foi
confirmado por resultados de simulacao.
4.5 Resultados de Simulacao 57
0
56
112
168
224
280
336
392
448
504
560
616
672
728
784
840
896
127 120 112 104 96 88 80 72 64 56 48 40 32 24 16 8 0
# te
stes
# nodos no estado falho
pior casomelhor caso
Figura 16: Numero de testes necessarios para um sistema com 128 nodos.
4.5.2 Latencia para Deteccao de Eventos
A latencia e o numero de rodadas de testes necessarias para que todos nodos sem-falha
realizem o diagnostico de um evento. O proposito desta serie de experimentos e verificar a
latencia para detectar um evento sob diferente situacoes de falhas. O primeiro experimento
conduzido foi em um sistema simulado de 512 nodos. Neste experimento inicialmente todos
os nodos estavam sem-falhas, entao o numero de nodos falhos era aumentado de 1 ate N−1.
Quando restava apenas um nodo sem-falha no sistema, os nodos eram sucessivamente
recuperados ate que todos os nodos se tornam-se novamente sem-falha. Este experimento
foi repetido 20 vezes medindo a latencia de 10200 eventos. O histograma na figura 18
mostra a distribuicao de frequencia da latencia observada para os eventos simulados. A
maioria dos eventos foi diagnosticada com um numero de rodadas cerca da latencia media
4.5 Resultados de Simulacao 58
0
128
256
384
512
640
768
896
1024
1152
1280
1408
1536
1664
1792
1920
2048
255 240 224 208 192 176 160 144 128 112 96 80 64 48 32 16 0
# te
stes
# nodos no estado falho
pior casomelhor caso
Figura 17: Numero de testes necessarios para um sistema com 256 nodos.
esperada, ou seja, cerca da media entre a latencia mınima (uma rodada) e latencia maxima
(log2N rodadas). Somando o numero de eventos diagnosticados em 3, 4 e 5 rodadas temos
8490 eventos, o que corresponde a 83.4% do numero de total de eventos simulados.
O mesmo experimento foi conduzido para sistemas com 32, 64, 128 e 256 nodos. O
grafico na figura 19 mostra a latencia observada para cada tamanho de sistema. As barras
mostram a latencia teorica maxima e mınima para cada tamanho de sistema. A linha
mostra a latencia observada com maior frequencia. Os resultados confirmam que a latencia
cresce de forma logarıtmica e que a maior dos eventos sao diagnosticados em cerca de
(log2N)/2 rodadas.
4.5 Resultados de Simulacao 59
0
500
1000
1500
2000
2500
3000
3500
987654321
Fre
quên
cia
Latência (rodadas)
148
518
1989
3628
2873
940
97 6 1
Figura 18: Latencia para sistemas com 512 nodos.
4.5.3 Comparacao com Outros Algoritmos
Nesta subsecao comparamos os resultados do novo algoritmo de diagnostico com os
algoritmos Hi-ADSD e Hi-ADSD com Timestamps. Os resultados apresentados para os
algoritmos Hi-ADSD e Hi-ADSD with Timestamps sao aqueles publicados em (DUARTE Jr.;
ALBINI; BRAWERMAN, 2000).
A tabela 3 mostra o numero medio de testes executados conforme o aumento de nodos
falhos. A primeira coluna apresenta o numero de nodos falhos, a segunda coluna o numero
medio de testes para o algoritmos Hi-ADSD with Timestamps, a terceira coluna o numero
de testes para o algoritmo de diagnostico baseado no DiVHA. O numero dentro de paren-
teses e o numero de testes adicionais necessarios, ou seja, o numero total de arestas no
grafo de testes menos o numero de arestas existente no hipercubo completo. Quando ha
poucos nodos falhos ambos algoritmos executam quase o mesmo numero de testes. Con-
forme aumenta o numero de nodos falhos o novo algoritmo apresenta um comportamento
4.5 Resultados de Simulacao 60
0
1
2
3
4
5
6
7
8
9
10
11
1024 512 256 128 64 32
Latê
ncia
(ro
dada
s)
Tamanho do sistema (nodos)
Figura 19: Latencia para sistemas com 32, 64, 128, 256, 512 e 1024 nodos.
Tabela 3: Numero medio de testes necessarios para diagnosticar um sistema com 64 nodos.
Nodos Hi-ADSD with DiVHAfalhos Timestamps
0 384 (0) 384 (0)1 378 (0) 378 (0)2 374 (2) 372 (0)4 369 (9) 360 (0)6 367 (19) 350 (2)12 350 (38) 316 (4)32 320 (128) 216 (24)
melhor que o Hi-ADSD with Timestamps. Com 32 nodos falhos no sistema, na media
o algoritmo DiVHA necessita apenas 24 testes adicionais, enquanto o algoritmo Hi-ADSD
with Timestamps requerer 128 testes adicionais. Isto representa uma diminuicao de 5 vezes
no numero de testes adicionais. Estes resultados mostram que a estrategia do algoritmo
DiVHA para minimizar o numero de arestas adicionais tem um impacto efetivo no numero
total de testes executados.
4.5 Resultados de Simulacao 61
Tabela 4: Latencia media para diagnosticar um evento em um sistema com 512 nodes.
Rodadas
Hi-ADSD 40Hi-ADSD withTimestamps 12
DiVHA 4
Outra comparacao realizada e quanto a latencia media para detectar um evento. E
considerado um sistema com 512 nodos onde um evento de falha ou recuperacao ocorre em
um dado nodo. Na tabela 3 podemos ver que em media o algoritmo DiVHA e 10 vezes
mais rapido que o Hi-ADSD original e 3 vezes mais rapido que o algoritmo Hi-ADSD com
Timestamps. Devemos notar que a definicao de rodadas de testes aplicada pelo algoritmo
DiVHA e diferente da empregada pelos outros algoritmos. Portanto o menor numero de
rodadas de testes nao implica em numa diminuicao no numero total de testes realizados
para diagnosticar um evento.
62
5 HyperBone: Uma Rede Overlay
Escalavel
O HyperBone e uma rede overlay formada por nodos espalhados pela Internet interliga-
dos por enlaces virtuais. Um enlace e implementado como uma conexao TCP persistente.
Se o numero de nodos e uma potencia de dois e todos os nodos estao funcionando sem
falhas, a topologia do sistema e um hipercubo completo. Quando o numero de nodos nao
e potencia de dois, ou alguns nodos nao estao disponıveis, o HyperBone ainda e capaz
de manter as propriedades logarıtmicas do hipercubo. O algoritmo DiVHA (Distributed
Virtual Hypercube Algorithm) e empregado, permitindo aos nodos calcular de forma in-
dependente seus enlaces virtuais na rede. Este capıtulo apresenta o modelo do sistema,
a especificacao do HyperBone, exemplos de execucao e os resultados obtidos da imple-
mentacao e experimentacao do sistema.
5.1 Modelo do Sistema
Considere um sistema S composto por um conjunto de N nodos, n0, n1,...,nN−1. Al-
ternativamente nos referimos ao nodo ni como nodo i. O sistema e considerado totalmente
conectado, ou seja, qualquer par de nodos pode se comunicar diretamente. Os relogios nao
sao sincronizados e nao sao feitas assercoes sobre as velocidades relativas dos processadores.
Um nodo ni pode assumir um de dois estados, working ou unresponsive. Um evento
e definido como a mudanca de estado de um nodo, tanto de working para unresponsive
como de unresponsive para working. A colecao dos estados de todos os nodos e o estado do
5.1 Modelo do Sistema 63
sistema. Se considera tambem um modelo dinamico para os estados do sistema, ou seja, os
nodos podem alternar entre o estado unresponsive e o estado working continuamente.
Os nodos sao capazes de realizar testes em outros nodos, assim um nodo testador
determina o estado do nodo testado. Os testes sao realizados periodicamente, dentro de
um intervalo de testes fixo, que pode variar dependendo da tecnologia do sistema, de alguns
poucos nanosegundos a varios minutos. Um nodo no estado working e considerado como
capaz de testar outros nodos e informar corretamente os resultados destes testes. Um teste
consiste em uma tarefa atribuıda pelo nodo testador ao nodo testado. A tarefa e executada
e o resultado devolvido para o testador que compara o resultado com o esperado. Um
intervalo de timeout e empregado para limitar a espera pelo resultado, a ocorrencia do
timeout e equivalente a uma resposta incorreta. Como o sistema e assıncrono, o timeout
nao e um indicativo concreto de que o nodo esta falho (crashed), assim um teste indica
apenas que o nodo ou esta funcionando corretamente ou nao respondeu corretamente a um
teste enviado ou ainda que nao respondeu dentro de um intervalo esperado.
Uma rodada de testes e definida como o perıodo de tempo em que todos os nodos
no estado working executam seus testes. A latencia do sistema e definida como o tempo
necessario para que todos nodos no estado working descubram a ocorrencia de um novo
evento.
Ainda consideramos que os nodos possam ser classificados em available e unavailable.
Um nodo available e um nodo que permanece no estado working por tempo suficiente para
ser considerado estavel e portanto disponıvel para receber tarefas. Um nodo unavailable e
um nodo que ainda nao pode ser considerado estavel, e por isso nao esta disponıvel para
receber tarefas. Cada nodo mantem informacoes sobre os estados de disponibilidade de
todos os outros nodos.
5.2 Construindo e Mantendo o Hipercubo Virtual 64
5.2 Construindo e Mantendo o Hipercubo Virtual
Seja o grafo de topologia virtual, tambem chamado Tv(S), um grafo direcionado cujos
nodos sao os nodos de S. Se existe uma aresta direcionada do nodo i para o nodo j,
entao existe um enlace virtual do nodo i para o nodo j. Atraves dos enlaces virtuais sao
trocadas as mensagens de testes, assim como roteadas as mensagens enviadas entre os
nodos. Cada nodo mantem uma tabela de roteamento que permita rotear uma mensagem
para um determinado destino. No HyperBone e proposta uma estrategia de roteamento
que permite determinar as rotas de menor custo no hipercubo virtual.
O algoritmo apresentado na figura 20 e executado a cada rodada de testes por todos
nodos no estado working para manter o hipercubo virtual. Este algoritmo de manutencao
do hipercubo virtual e baseado no algoritmo de diagnostico apresentado na figura 11 da
secao 4.2. Sao inseridas no algoritmos as estruturas necessarias para estabelecer os enlaces
virtuais entre os nodos, manter a tabela de roteamento e determinar a lista de nodos
estaveis. O algoritmo DiVHA usado para determinar a topologia do hipercubo virtual
dado o estado percebido do sistemas e aquele apresentado na secao 4.3.
A cada rodada de testes os nodos no estado working executam seus testes, ou seja,
testam os nodos pertencentes a t(i) que e o conjunto de nodos adjacentes ao nodo i em
Tv(S). Se um nodo i testa um dado nodo j e preciso criar o enlace virtual ligando o nodo
i ao nodo j. Este enlace virtual e implementado como uma conexao TCP/IP. Uma falha
ao criar o enlace virtual, estabelecer a conexao TCP/IP, equivale a testar um nodo como
unresponsive.
Para atualizar a informacao de estado do sistema, quando o nodo i testa um nodo j
no estado working ele obtem informacao sobre todos os nodos k com distancia de j menor
ou igual a log2N − 1, ou seja k ∈ Dj,log2N−1, tal que dj,k < di,k. Alem da informacao de
diagnostico, tambem e obtida informacao de roteamento deste conjunto de nodos. Quando
um nodo detecta um evento, ele executa o algoritmo DiVHA, apresentado na secao 4.3, que
5.2 Construindo e Mantendo o Hipercubo Virtual 65
HyperBone Construct ion & MaintenanceTv(S)=DiVHA(S)DO
FOR EACH j IN t ( i )IF i i s not connected to j THEN
cr ea t e v i r t u a l l i n k between i and jIF i i s connect to j THEN
t e s t ( j )ELSE
j i s unrespons iveIF the s t a t e o f t e s t ed node has changed THEN
update s t a tu s in fo rmat ion about jIF node j i s working THEN
get from j d i a gno s i s and rout ing in fo rmat ion aboutnodes k in Dk, logN−1 such that d( j , k ) < d( i , k )
update l o c a l in fo rmat ion comparing timestampsupdate l o c a l rout ing in fo rmat ion
IF new events have been d i s cove r ed THENupdate T(S) with DiVHA
END FORupdate a v a i l a b l e / unava i l ab l e nodes l i s tSLEEP un t i l the next Test ing I n t e r v a l
FOREVER
Figura 20: O algoritmo para criacao e manutencao do hipercubo virtual.
determina o novo conjunto de testes que devem ser executados pelo nodo. Os algoritmos
para atualizar as informacoes de roteamento e para determinar os estados de disponibilidade
sao apresentados nas subsecoes seguintes.
5.2.1 Algoritmo de Roteamento no Hipercubo Virtual
O HyperBone e capaz de rotear mensagens entre os nodos atraves dos enlaces virtuais.
A cada rodada, alem de atualizar as informacoes de estado de sistema, tambem e atualizada
a informacao de roteamento. O algoritmo de roteamento e apresentado na figura 21. O
vetor route mantem a tabela de roteamento, ou seja, determina o proximo salto para rotear
uma mensagem para um determinado nodo. O vetor rcost mantem uma estimativa de
custo para atingir cada nodo do sistema dada a rota atual.
Quando um nodo i testa um nodo j como working, o custo do enlace i → j e estimado e
a informacao de custo para atingir o nodo j atualizada. Alem disso, sao obtidas informacoes
5.2 Construindo e Mantendo o Hipercubo Virtual 66
da tabela de custos do nodo j (rcost_j). Para cada nodo k que pode ser alcancado pelo
nodo i passando pelo nodo j uma comparacao de custo e realizada. Se o custo atual de
alcancar um nodo k (rcost[k]) for maior que o custo de alcancar este nodo k passando
pelo nodo j (rcost[j] + rcost_j[k]) entao o nodo j representa a melhor rota atual para
o nodo k. Neste caso informacao de custo e atualizada e a tabela local de roteamento passa
a apontar o nodo j como a nova rota para o nodo k.
HyperBone Routing Table Maintenance at node iroute keeps the rout ing tab l er c o s t keeps the es t imate co s t to reach a given nodeWHEN updating in fo rmat ion from node j
r c o s t [ j ] = co s t measured from node i to node jr c o s t j = GET rout ing co s t t ab l e from node JFOR EACH node k in Dk, logN−1 such that dj , k < di , k
IF ( r c o s t [ k ] > r c o s t [ j ]+ r c o s t j [ k ] )r c o s t [ k ] = r c o s t [ j ]+ r c o s t j [ k ]route [ k ] = j ;
END IFEND FOR
END
Figura 21: Algoritmo de manutencao da tabela de rotas no HyperBone.
No algoritmo de roteamento proposto neste trabalho o numero de saltos necessario
para rotear uma mensagem para qualquer nodo nunca e maior que log2N . Alem disto, a
rota e escolhida de forma a minimizar o custo. Estas propriedades sao fundamentais para
implementar servicos de busca de objetos e/ou comunicacao ponto a ponto ou em grupo
de forma eficiente usando o HyperBone.
A figura 22 mostra um exemplo de execucao do algoritmo de roteamento para um
sistema com 8 nodos. No exemplo, e mostrado o comportamento do algoritmo para o nodo
7. O nodo 3, o nodo 5 e o nodo 6 estao diretamente conectados ao nodo 7, entao eles
simplesmente testam o nodo 7 e estimam o custo do enlace. Por exemplo, o custo estimado
do enlace do nodo 3 para o nodo 7 e 40 ms. O nodo 2 pode alcancar o nodo 7 tanto pelo
nodo 3 como pelo nodo 6. O custo do nodo 2 para o nodo 3 e 30 ms, e o custo do nodo 3
para o nodo 7 e 40 ms, entao o custo da rota do nodo 2 para o nodo 7 passando pelo nodo
3 e 70 ms. Da mesma maneira, o custo da rota do nodo 2 para o nodo 7 passando pelo
5.2 Construindo e Mantendo o Hipercubo Virtual 67
nodo 6 e 110 ms. Assim, a tabela de roteamento do nodo numero 2 vai indicar o nodo 3
como melhor rota para o nodo 7. Como exemplo final, o nodo 0 tem 3 possıveis rotas para
o nodo 7: nodo 1, com custo 50 ms mais 110 ms; node 2 com custo de 10 ms mais 70 ms
e nodo 7 com custo 130 ms mais 20 ms. Portanto a rota com menor custo do nodo 0 para
o nodo 7 e aquela passando pelo nodo 2 que tem custo total de 80 ms. Com a tabela de
rota construıda neste exemplo, uma mensagem do nodo 0 para o nodo 7 primeiro e enviada
para o nodo 2, entao para o nodo 3 e entao finalmente chega ao nodo 7.
Figura 22: Exemplo de roteamento para um sistema com 8 nodos no HyperBone.
5.2.2 Parametros de Disponibilidade
Consideramos que os nodos podem passar por perıodos de instabilidade que causam
falhas de desempenho, fazendo com que seu estado alterne entre unresponsive e working.
Dada esta assercao, considere duas situacoes: a) um nodo que vem continuamente res-
pondendo corretamente aos testes, falha ao responder corretamente um teste, voltando em
seguida a responder os testes corretamente. Boa parte das aplicacoes poderia suportar um
5.2 Construindo e Mantendo o Hipercubo Virtual 68
pequeno perıodo, evitando assim o possıvel custo de considerar o nodo como falho; b) em
outra situacao, um nodo apenas responde corretamente aos testes por pequenos intervalos
de tempo. Este nodo nao deveria ser considerado como disponıvel em nenhum momento, ja
que nao consegue atender os requisitos dos testes por um perıodo de tempo razoavel. Com
o objetivo de tratar estes casos, este trabalho introduz os parametros de disponibilidade
que permitem classificar os nodos em available e unavailable.
Os parametros de disponibilidade sao definidos por um perıodo mınimo de tempo pre-
definido em que o nodo deve permanecer no estado working para ser considerado available, e
por um perıodo mınimo de tempo que o nodo deve permanecer no estado unresponsive para
ser considerado unavailable. Esta estrategia facilita a monitoracao de sistemas altamente
instaveis, com mudancas contınuas de estado dos nodos. Cada nodo mantem informacoes
sobre os estados de disponibilidade de todos os outros nodos.
A figura 23 mostra o algoritmo executado pelo HyperBone ao final de cada rodada,
com o objetivo de manter as informacoes sobre os estados de disponibilidade dos nodos.
O estado de cada nodo e verificado, se um nodo permancer no estado working por um
intervalo de tempo mınimo Wt entao este nodo e considerado como available. De maneira
analoga, se um nodo permanecer por um intervalo de tempo Ut no estado unresponsive e
considerado como unavailable. Se nenhuma destas condicoes se verificar, o nodo mantem
o estado de disponibilidade anterior. Os intervalos de tempo Wt e Ut sao parametros do
sistema e dependem dos requisitos das tarefas que se pretende executar.
HyperBone a v a i l a b i l i t y in fo rmat ion maintainance a lgor i thm at node iFOR each node i =0 . . .N−1 do
IF node i i s working f o r the g iven Wt time THENnode i as a v a i l a b l e
IF node i i s unrespons ive f o r the g iven Ut time THENnode i as unava i l ab l e
END
Figura 23: Algoritmo de atualizacao das informacoes sobre os estados de disponibilidade.
5.3 Exemplos de Execucao 69
5.3 Exemplos de Execucao
Esta secao apresenta exemplos de execucao do HyperBone e do algoritmo DiVHA.
Considere um sistema com 16 nodos, e o estado inicial ilustrado na figura 24.a, na qual os
nodos em cinza estao no estado unresponsive. As arestas finas sao as arestas do hipercubo,
as arestas grossas indicam arestas adicionadas pelo DiVHA. A figura 24.b mostra o fluxo
de informacoes de estados do sistema para o nodo 0, os nodos agrupados representam o
conjunto de nodos sobre os quais o nodo 0 obtem informacao durante os testes, por exemplo
ao testar o node 3, o nodo 0, obtem informacoes sobre o nodo 11, nodo 15 e nodo 7.
a:Enlaces do overlay. b:Fluxo de informacoes para o nodo 0.
Figura 24: Exemplo de sistema com 16 nodos executando o HyperBone.
Suponha que o nodo 4 se torne unresponsive, cada nodo ao obter o novo estado do nodo
4 executa o DiVHA determinando a nova topologia do sistema. A figura 25 representa a
execucao do DiVHA a cada iteracao s. Na primeira iteracao sao adicionadas arestas para
formar caminhos com tamanho ≤ 1 entre todo nodo i e os clusters Ci,0, essa iteracao e trivial
incluindo apenas arestas do hipercubo. A iteracao (2) garante caminhos com tamanho ≤ 2
para clusters Ci,2. Nessa iteracao se verifica a inexistencia de caminhos entre nodo 0 e nodo
3, nodo 3 e nodo 0, nodo 9 e nodo 10, e nodo 10 e nodo 9, assim sao adicionadas as arestas
0 → 3, 3 → 0, 0 → 9, 9 → 0. A iteracao (3) garante caminhos com tamanho ≤ 3 para
5.3 Exemplos de Execucao 70
os clusters Ci,3, no caso nao sao necessarias arestas alem das convencionais do hipercubo.
Finalmente, na iteracao (4) sao incluıdas as arestas 0 → 9, 9 → 0, 6 → 10 e 10 → 6 para
garantir os caminhos de tamanho 4 entre esses nodos.
iteracao 1 iteracao 2 interacao 3 interacao 4
Figura 25: Representacao das iteracoes do algoritmo DiVHA.
A figura 26.a mostra o hipercubo virtual final para o sistema com o nodo 4 falho. As
arestas mais grossas indicam arestas adicionais, sendo que as arestas pontilhadas represen-
tam os testes adicionais que ja existiam antes da falha do nodo 4. A figura 26.b mostra a
nova configuracao do fluxo de informacoes para o nodo 0.
a:Enlaces do overlay. b:Fluxo de informacoes para o nodo 0.
Figura 26: Exemplo de sistema com 16 nodos apos falha do nodo 4.
5.4 Implementacao e Resultados Experimentais 71
5.4 Implementacao e Resultados Experimentais
O HyperBone foi implementado como daemons de rede que executam em cada nodo
agregado ao sistem. Os nodos se comunicam atraves de conexoes TCP/IP permanentes,
correspondentes aos enlaces virtuais definidos pelo algoritmo DiVHA. Os testes consistem
no envio de uma mensagem para o nodo testado que deve ser respondida dentro de um
perıodo de tempo definido.
Um aspecto importante da implementacao e que o HyperBone e transparente para as
aplicacoes. Se uma aplicacao deseja se comunicar atraves do hipercubo virtual basta que use
enderecos IP exclusivamente (Internet Protocol) alocados para o HyperBone. Por exemplo,
se a rede 10.0.0.0/8 esta reservada para o HyperBone, basta a aplicacao usar enderecos
desta faixa para se comunicar usando o hipercubo virtual. Esse recurso e implementando
atraves da interface tun/tap (TUNTAP, 2005) que implementa um dispositivo de rede virtual
que forca o recebimento de pacotes de uma aplicacao em espaco de usuario, ao inves de
recebe-los do protocolo da camada de enlace.
O ambiente de experimentacao escolhido foi o PlanetLab (PLANETLAB, 2005), que e
um ambiente composto por computadores distribuıdos em todo mundo conectados pela In-
ternet, atualmente contando com 631 maquinas em mais de 25 paıses. Os experimentos se
destinaram a avaliar o HyperBone no aspecto de estabilidade, sistema de monitoracao, sis-
tema de comunicacao/roteamento e capacidade de execucao de aplicacoes. Os experimentos
realizados e os resultados obtidos sao descritos nas proximas subsecoes.
5.4.1 Sistema de Monitoracao
Para avaliar o sistema de monitoracao o HyperBone foi instalado em 128 maquinas
do PlanetLab e sua execucao acompanhada durante cerca de 3 semanas. Os sistema foi
executado com diversos parametros, ao final considerando os tempos medios de resposta
no PlanetLab conclui-se que um valor de timeout adequado seria de 7 segundos e o inter-
5.4 Implementacao e Resultados Experimentais 72
valo entre os inıcios de duas rodadas de testes foi fixado em 10 segundos. Os resultados
apresentados sao relativos aos dados obtidos do registro de execucao do sistema com estes
parametros durante 6 dias.
Um dos experimentos realizados visou descobrir o tempo em que os nodos permanecem
em um dado estado antes de sofrerem um novo evento. Considerando o timeout relati-
vamente pequeno para a carga do PlanetLab, os nodos nao eram capazes de atender por
perıodos longos e contınuos os requisitos temporais impostos pelos testes, o resultado e
que foi detectado um grande numero de eventos. Registramos cerca de 200 mil eventos em
6 dias o que representa uma taxa aproximada de 1388 eventos/hora. O grafico da figura
27 mostra a distribuicao acumulada para o tempo de permanencia nos estados working e
unresponsive antes da ocorrencia de um novo evento. Podemos observar que, na grande
maioria dos casos, os nodos permaneceram working por menos de 10 minutos e unresponsive
por menos de 120 segundos.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
6d3d1d10h5h2h1h30 min10 min5 min2min1min30s15s10s6s4s3s2s1s
Pro
babi
lidad
e ac
umul
ada
Tempo de permanência no estado
unresponsiveworking
Figura 27: Probabilidade acumulada para o tempo de permanencia nos estados working eunresponsive.
5.4 Implementacao e Resultados Experimentais 73
O grande numero de eventos registrados justificou na pratica a utilidade dos parametros
de estabilizacao introduzidos no HyperBone. Baseado nos tempos observados no grafico da
figura 27 decidiu-se considerar um nodo unavailable apenas apos permanecer 120 segundos
no estado unresponsive, e considerar um nodo available apos permanecer 600 segundos no
estado working. Com esses parametros o numero de eventos percebidos para os estados
unavailable e available foi de apenas 1050, ou seja, uma taxa menor que 8 eventos/hora,
numeros significativamente reduzidos considerando o resultado acima descrito.
Na pratica esta forma de classificar os nodos permite descobrir o conjunto de nodos
que apresentam comportamento mais estavel em comparacao aos outros. Pode-se dizer que
aumenta a granularidade com que se enxerga o estado do sistema. Por exemplo, um nodo
available apenas deixa de ser considerado available se passar mais que 120 segundos como
unresponsive; um nodo unavailable apenas sera considerado available se passar por mais de
600 segundos sendo considerado working.
Desta forma, nodos que ficam silenciosos por pequeninos intervalos de tempo tambem
sao considerados estaveis. O grafico da figura 28 mostra a probabilidade acumulada para o
tempo de permanencia nos estados available e unavailable. Observamos perıodos maiores
em que nodos permanecem em um unico estado, por exemplo, em cerca de 40% dos casos
os nodos permaneceram mais de 1 hora no estado available antes de um evento e em 80%
dos casos os nodos permaneceram mais que 30 minutos no estado unavailable.
Outra medida obtida foi a taxa de disponibilidade dos nodos baseada nos estados
available e unavailable. O histograma da figura 29 mostra a distribuicao de frequencia da
disponibilidade dos nodos. Apesar das instabilidades do sistema observamos que 47 nodos
apresentaram disponibilidade entre 80% e 90% e 20 nodos acima de 90%. As taxas de
disponibilidade muito baixas foram relativas a nodos que estavam inacessıveis ou falhos.
Por fim, examinamos os limites de tempo para a propagacao dos eventos no hipercubo.
Escolhemos um perıodo e um nodo que estivesse alternando repetidamente de estado, e
5.4 Implementacao e Resultados Experimentais 74
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
6d3d1d10h5h2h1h30 min10 min5 min2min
Pro
babi
lidad
e ac
umul
ada
Tempo de permanência no estado
unavaliableavaliable
Figura 28: Probabilidade acumulada para o tempo de permanencia nos estados available eunavailable.
observamos o estado deste nodo a partir de outros nodos com diferentes distancias no
hipercubo. O nodo 4 teve seus eventos observados, os pontos de observacao foram: nodo
5 a distancia 1, nodo 7 a distancia 2, nodo 77 a distancia 3, nodo 118 a distancia 4, nodo
44 a distancia 5, nodo 122 a distancia 6 e finalmente nodo 123 a distancia 7, a maior
possıvel tendo em vista o numero total de nodos do hipercubo, 128. A figura 30 mostra os
resultados obtidos, o relogio utilizado para registrar os eventos foi o relogio das maquinas,
que estava sincronizado por NTP (Network Time Protocol). Pode-se comprovar por estes
resultados que os nodos obtem as informacoes dentro do intervalo de tempo esperado.
5.4.2 Estrategia de Roteamento no HyperBone
O proposito deste experimento foi avaliar a estrategia de roteamento empregado pelo
HyperBone. Para este experimentos, instalamos o HyperBone em 256 maquinas do Plane-
tLab. O sistema foi inicializado e deixado em execucao por um dado perıodo de tempo, e
5.4 Implementacao e Resultados Experimentais 75
0
5
10
15
20
25
30
35
40
45
50
0.9−10.8−0.90.7−0.80.6−0.70.5−0.60.4−0.50.3−0.40.2−0.30.1−0.20−0.1
Núm
ero
de n
odos
Taxa de disponibilidade
Figura 29: Histograma da taxa de disponibilidade dos nodos.
entao um snapshot do sistema foi tirado. O snapshot obteve informacao sobre a topologia
virtual atual e os custos estimados de cada enlace virtual.
Com estes dados, foram obtidos os custos para todas as possıveis rotas com o menor
numero de saltos entre todos os pares de nodos do sistema. A tabela 5 mostra a com-
paracao do custo da rota escolhida pelo HyperBone, com o custo destas outras possıveis
rotas. Cada coluna representa os resultados obtidos para rotas com um dado tamanho. A
primeira linha compara o custo da rota de maior custo entre dois nodos com o custo da
rota determinada pelo HyperBone. De maneira similiar, a segunda linha compara o custo
medio das rotas entre dois nodos com o custo da rota determinada pelo HyperBone. Os
resultados apresentados sao obtidos da media destas comparacoes para todos os possıveis
pares de nodos. Para pares de nodos que estao a distancia 1 existe apenas uma rota, as-
sim a rota escolhida pelo HyperBone e a unica possıvel. Conforme a distancia entre os
nodos aumenta o numero de possıveis rotas tambem aumenta e se percebe a vantagem da
estrategia de roteamento do HyperBone. Para rotas com tamanho 8, na media as rotas do
HyperBone tem um custo 8,71 vezes menor que a pior rota possıvel, e 3,32 vezes menor
que o custo medio das rotas disponıveis. Estes resultados mostram que a estrategia de
5.4 Implementacao e Resultados Experimentais 76
working
faulty
working
faulty
working
faulty
working
faulty
working
faulty
working
faulty
working
faulty
12h11h10h9h8h7h6h5h4h3h2h1h
tempo (s)
Nodo 5 Nodo 7 Nodo 77 Nodo 118 Nodo 44 Nodo 122 Nodo 123
Figura 30: Propagacao da informacao de um evento no nodo 4.
roteamento do HyperBone tem realmente um forte impacto no custo total de roteamento.
Tabela 5: Relacao de ganho da estrategia de roteamento do HyperBone.
Numero de saltos da rota1 2 3 4 5 6 7
Pior caso 1:1 1:2,06 1:2,88 1:4,11 1:5,54 1:7,07 1:8,71Media 1:1 1:1,53 1:1,87 1:2,27 1:2,64 1:2,97 1:3,32
5.4.3 Executando Aplicacoes Paralelas no HyperBone
A capacidade de execucao de aplicacoes no HyperBone foi avaliada executando aplicacoes
paralelas usando MPI. Nestes experimentos foi utilizado um hipercubo virtual formado por
256 maquinas do PlanetLab. A cada teste, baseado nas informacoes de monitoracao dispo-
nibilizadas pelo HyperBone, se selecionava no hipercubo virtual o conjunto de nodos que
apresentava o comportamento mais estavel.
O objetivo do primeiro experimento foi comprovar o funcionamento das primitivas de
5.4 Implementacao e Resultados Experimentais 77
comunicacao do MPI sobre o HyperBone. Foi utilizado o MPIbench (MPIBENCH, 2005),
um benchmark que exercita as principais funcoes do MPI, tanto de comunicacao ponto a
ponto (MPI_Send e MPI_Receive) como de comunicacao em grupo, por exemplo difusao
(MPI_Broadcast). A tabela 6 apresenta o resultado da execucao do MPIbench. Cada
coluna representa os resultados de um tipo de teste do MPIbench, as linhas mostram
o tamanho de mensagens utilizado em cada teste. O resultado a ser observado nao e
o desempenho propriamente dito, mas sim o fato dos testes terem sido executados com
sucesso e sem necessidade de modificar a aplicacao mesmo num ambiente instavel como o
PlanetLab.
Tabela 6: Resultados da execucao do MPIbench no HyperBone.
Tamanho da Latencia Biband Roundtrip Bandwidth Broadcast Reduce Alltoall AllReduceMensagem µ s KB/s trans./s KB/s KB/s KB/s KB/s KB/s
8192 25650.24 259.97 11.83 232.29 54.81 21.11 100.40 17.8516384 43234.49 420.03 8.12 312.55 47.13 32.10 100.80 22.4632768 82235.52 552.82 5.13 341.39 34.26 32.19 121.13 15.4865536 207180.25 567.78 2.53 375.95 36.26 37.48 98.11 20.09
O segundo experimento realizado teve como objetivo verificar a possibilidade de execu-
tar aplicacoes reais em MPI usando o HyperBone. Foi executada uma aplicacao em MPI
que paraleliza a tarefa de encontrar uma senha em um determinado espaco de busca. A
tabela 7 mostra taxa de chaves avaliada por segundo obtida em sistemas com 16, 32 e 64
nodos. Podemos observar que o sistema teve uma escalabilidade razoavel tanto de 16 para
32 nodos, como de 32 para 64 nodos.
Tabela 7: Resultado da execucao de um buscador de senhas no HyperBone.
Nodos Senhas por segundo
16 31368.1432 42968.3364 50200.20
5.4 Implementacao e Resultados Experimentais 78
5.4.3.1 Dispositivo MPI para o HyperBone
Um outro conjunto de experimentos executando aplicacoes distribuıdas paralelas foi
executado. No lugar de usar a implementacao do HyperBone baseada na interface TUN/TAP,
foi utilizado o ch hyperbone. O ch hyperbone utiliza dispositivos do MPI chamados ADI
(Abstract Device Interface)(CROPP, 1995) que abstrai o transporte das mensagens per-
mitindo as aplicacoes em MPI acessarem diretamente o hipercubo virtual. O objetivo
destes experimentos foi avaliar a possibilidade de utilizar o HyperBone como alternativa
para execucao de programas MPI em ambientes de grade e/ou sujeito a falhas. Com
ch hyperbone seria possıvel modificar o comportamento das primitivas de comunicacao
MPI, permitindo implementar sistemas MPI adaptados a grades computacionais e tambem
tolerantes a falha.
Os experimento realizados com o ch hyperbone foram realizados usando maquinas de
um cluster de estacoes, interligado por interfaces de rede ethernet de 1Gbps. Um dos
experimento realizados mediu o impacto do roteamento das mensagens atraves do hiper-
cubo, os resultados obtidos foram comparados com o dispositivo ch p4, que e o ADI padrao
utilizado em redes TCP/IP. A vazao foi medida utilizando o tempo de execucao de um
programa que usa as primitivas do MPI para transferir 100.000 mensagens de 8KB cada.
Para o ch hyperbone foi medida a vazao entre pares de nodos a diferentes distancias no
hypercubo. A vazao atingida com o ch p4 foi medida apenas entre dois nodos.
Os resultados do teste de vazao sao apresentados na tabela 8. A primeira coluna repre-
senta a vazao obtida com o dispositivo ch p4. As colunas seguintes a vazao obtida com o
ch hyperbone para nodos a diferente distancias no hipercubo. A vazao atingida nos experi-
mentos pelo ch hyperbone em relacao ao ch p4 variou de 96,32%, para nodos diretamente
conectados, diminuindo gradativamente para 50,22% com nodos a distancia 4. Como espe-
rado, o roteamento das mensagens e a camada ADI resultam em um overhead no sistema.
Entretanto, deve se considerar que muitos algoritmos paralelos sao baseadas no hipercubo,
5.4 Implementacao e Resultados Experimentais 79
ou em estruturas contidas no hipercubo, diminuindo a necessidade de comunicacao entre
nodos distantes no hipercubo. Alem disto, o crescimento do custo de roteamento e apenas
logarıtmico, ja que as rotas tem distancia maxima log2N . Desta forma, estes resultados
mostram a viabilidade de utilizar do hipercubo virtual como plataforma para execucao do
aplicacoes em MPI na Internet.
Tabela 8: Comparativo de vazao entre os dispositivos ch hyperbone e ch p4.
ch p4 ch hyperbone1 1 2 3 4
Vazao (Mbps/s) 653.97 629.17 474.72 463.67i 328.07
Outro experimento executado foi executando o MPI-PovRay (MPI-POVRAY, 2003), que
e um software de renderizacao de imagens baseado na estrutura mestre-escravo. Foram
realizados experimentos comparando o tempo de renderizacao de imagem de 1000x500
pixels utilizando o ch hyperbone e o ch p4. Os experimento foram realizados em sistemas
com 2, 4, 8 e 16 nodos. A tabela 9 apresenta os resultados do tempo de execucao do MPI-
PovRay. As colunas representam o numero de nodos no sistema. A primeira linha apresenta
o tempo de execucao em segundos para o ch hyperbone. A segunda linha apresenta o tempo
de execucao em segundos para o ch p4. Verificamos que os tempos de execucao sao muito
similares, mostrando que em aplicacoes onde o tempo de processamento domina o tempo
de comunicacao, o custo de utilizar hipercubo virtual pode ser desprezıvel.
Tabela 9: Comparativo do tempo de execucao do MPI-PovRay entre os dispositivosch hyperbone e ch p4.
Numero de nodos2 4 8 16
ch hyperbone 111,66 s 37,66 s 17 s 10,33 sch p4 109,33 s 36.0 s 20,33 s 11 s
O conjunto de experimentos realizados com o ch hyperbone mostram a viabilidade da
utilizacao do hipercubo virtual como rede overlay para aplicacoes MPI. O ch hyperbone
5.4 Implementacao e Resultados Experimentais 80
poderia ser utilizado para prover implementacoes MPI adaptadas ao ambiente de grades,
integrando o sistema com ambientes de grades como o Globus, ou ainda prover tolerancia
a falhas.
81
6 Conclusao
Este trabalho apresentou o HyperBone, uma rede overlay que aproveita caracterısticas
topologicas do hipercubo para oferecer servicos escalaveis de comunicacao e monitoracao
para sistemas distribuıdos em larga escala na Internet. O HyperBone implementa um
hipercubo virtual que e reconfigurado dinamicamente para se adaptar as constantes falhas,
recuperacoes e perıodos de instabilidade apresentados pelos nodos do sistema.
O HyperBone e baseado no algoritmo DiVHA, tambem proposto neste trabalho. O
algoritmo DiVHA e utilizado pelo HyperBone e permite que os nodos do sistema man-
tenham, de forma distribuıda, independente e determinıstica, a topologia do hipercubo
virtual, garantido duas propriedade: (1) diametro logaritmico, a distancia entre qualquer
par de nodos e menor ou igual a log2N ; (2) numero maximo de enlaces e Nlog2N . O
DiVHA foi especificado e foram apresentadas as provas formais de correcao do algoritmo.
Um novo algoritmo de diagnostico distribuıdo baseado no DiVHA tambem foi proposto,
especificado e formalmente provado neste trabalho. Este novo algoritmo oferece um sis-
tema de monitoracao distribuıda que permite aos nodos sem falha determinar o estado de
todos os outros nodos do sistema em no maximo log2N rodadas de testes, requerendo no
maximo N ∗ (log2N)2 testes. Resultados experimentais obtidos por simulacao tambem fo-
ram apresentados, comparando o algoritmo de diagnostico baseado no DiVHA com outros
algoritmos de diagnostico similares.
Os nodos do sistema utilizam o HyperBone para se comunicar, todas as mensagens
trocadas entre os nodos sao tuneladas e roteadas atraves dos enlaces do hipercubo virtual,
6 Conclusao 82
permitindo a qualquer par de nodos se comunicar atraves de rotas com distancia maxima
igual a log2N enlaces. Uma estrategia de roteamento que permite determinar as melhores
rotas disponıveis no hipercubo virtual tambem foi proposta. Resultados experimentais
demonstram que as rotas determinadas pelo algoritmo de roteamento podem apresentar
um custo de 8,71 vezes menor que outras rotas no hipercubo.
O HyperBone tambem introduziu uma estrategia para lidar com sistemas nos quais
os nodos apresentam comportamento bastante instavel, alternando frequentemente entre
estados. Esta estrategia classifica os nodos em nodos em available e unavailable e introduz
os parametros de disponibilidade. Estes parametros sao definidos por um perıodo mınimo de
tempo pre-definido em que o nodo deve permanecer no estado working para ser considerado
available, e por um perıodo mınimo de tempo que o nodo deve permanecer no estado
unresponsive para ser considerado unavailable. Isto permite determinar os nodos que estao
apresentando comportamento mais estavel e tem a maior probabilidade de ser utilizados
para tarefas de processamento.
O HyperBone foi implementado utilizando a interface tun/tap provendo uma rede over-
lay transparente para as aplicacoes. O sistema foi testado no PlanetLab que oferece um am-
biente dinamico com os nodos sujeitos a altas carga de processamento e rede. Um conjunto
de testes avaliou o sistema de monitoracao, o HyperBone foi instalado em 128 maquinas
do PlanetLab e sua execucao acompanhada durante cerca de 3 semanas. Estes experi-
mentos avaliaram a funcionalidade do sistema e comprovaram a utilidade dos parametros
de disponibilidade. Outro conjunto de experimentos verificou a possibilidade de execu-
tar aplicacoes paralelas em usando o HyperBone. O ch hyperbone, uma implementacao
alternativa do HyperBone baseada na camada ADI do MPI, tambem foi avaliada.
Trabalhos futuros incluem a implementacao de primitivas de comunicacao em grupo
no hipercubo virtual, permitindo realizar difusao e multicast de forma eficiente. Outro
trabalho futuro e a integracao do HyperBone com um sistema de buscas de informacao,
implementando a busca de forma a tirar proveito da topologia. A integracao do HyperBone
6 Conclusao 83
com uma arquitetura de grades, como o Globus, e outro possıvel trabalho futuro. Final-
mente, outra perspectiva de trabalho e a integracao de mecanismos de tolerancia a falhas
no HyperBone, permitindo a execucao de aplicacoes de longa vida na Internet.
84
Referencias
AGBARIA, A.; FRIEDMAN, R. Starfish: Fault-tolerant dynamic MPI programs onclusters of workstations. 8th International Symposium on High Performance DistributedComputing, p. 167–176, 1999.
ALVISI, L.; MARZULLO, K. Message logging: Pesimistic, optimistic, causal and optimal.15th International Conference on Distributed Computing Systems (ICDSS 1995), p.229–236, 1995.
AMIR, Y.; DANILOV, C. Reliable communication in overlay networks. InternationalConference on Dependable Systems and Networks (DSN 2003), p. 511–520, 2003.
ANDERSEN, D. G.; BALAKRISHNAN, H.; MORRIS, M. F. K. R. Resilient overlaynetworks. Operating Systems Review, p. 131–145, 2001.
BALAKRISHNAN, H. et al. Looking up data in P2P systems. Communications of theACM, v. 46, n. 2, p. 43–48, 2003.
BATCH, R. et al. MPI/ft: Architecture and taxonomies for fault-tolerant. 1st IEEEInternational Symposium of Cluster Computing and the Grid, p. 26–33, 2001.
BEISEL, T.; GABRIEL, E.; RESCH, M. An extension to MPI for distributed computingon MPPs. Lecture Notes in Computer Science, p. 75–82, 1997.
BIANCHINI, R. P.; BUSKENS, R. An adaptive distributed system-level diagnosisalgorithm and its implementation. 21st International Symposium on Fault-TolerantComputing, p. 222–229, 1991.
BIANCHINI, R. P.; BUSKENS, R. Implementation of on-line distributed system-leveldiagnosis theory. IEEE Transactions on Computers, v. 41, p. 616–626, 1992.
BLOUGH, D. M.; BROWN, H. W. The broadcast comparison model for on-line faultdiagnosis in multicomputer systems: Theory and implementation. IEEE Transactions onComputers, v. 48, p. 470–493, 1999.
BOLOSKY, W. J. et al. Feasibility of a serveless distributed file system deployed on anexisting set of desktop PCs. ACM international conference on Measurement and modelingof computer systems, SIGMETRICS, p. 34–43, 2000.
BOLSICA, G. et al. Mpich-v: Towards a scalable fault tolerant MPI for volatile nodes. p.1–18, 2000.
Referencias 85
BONA, L. C. E.; DUARTE Jr., E. P.; FONSECA, K. V. O. Uma arquitetura de gradebaseada em hipercubo virtual. 3o Workshop de Computacao em Grids e Aplicacoes(WCGA), p. 1–5, 2005.
BONA, L. C. E.; DUARTE Jr., E. P.; FONSECA, K. V. O. Self diagnosis based on thedistributed virtual hypercube algorithm. The Latin American Autonomic ComputingSymposium (LAACS), 2006.
BONA, L. C. E. et al. Hyperbone: Uma rede overlay baseada em hipercubo virtual sobrea internet. 24o. Simposio Brasileiro de Redes de Computadores (SBRC), 2006.
BOUTEILLER, A. et al. MPICH-V2: A fault tolerant MPI for volatile nodes basedon pessimistic sender based message logging. IEEE/ACM SC 2003: High PerformanceNetworking and Computing, p. 25–25, 2003.
BOUTEILLER, A. et al. Coordinated checkpoint versus message log for fault tolerantMPI. IEEE International Conference on Cluster Computing (CLUSTER’03), p. 242–250,2003.
CHANDY, K. M.; LAMPORT, L. Distributed snapshots: Determining global states ofdistributed systems. Transactions on Computer Systems, v. 3, n. 1, p. 63–75, 1985.
CLARK, D. Face-to-face with peer-to-peer networking. IEEE Computer, v. 34, n. 1, p.18–21, 2001.
CROPP, W. Abstract device interface specification. Argonne National Laboratory, 1995.
DOVAL, D.; O’MAHONY, D. Overlay networks: A scalable alternative for P2P. IEEEInternet Computing, v. 7, n. 3, p. 2–5, 2003.
DUARTE Jr., E. P.; ALBINI, L. C. P.; BRAWERMAN, A. An algorithm for distributeddiagnosis of dynamic fault and repair events. 7th IEEE International Conference onParallel and Distributed Systems, IEEE/ICPADS’00, p. 299–306, 2000.
DUARTE Jr., E. P.; BRAWERMAN, A.; ALBINI, L. C. P. A diagnosis algorithm basedon clusters with detours. Available at http://www.inf.ufpr.br/ elias., 1998.
DUARTE Jr., E. P. et al. Non-broadcast network fault-monitoring based on system-leveldiagnosis. 5th IFIP/IEEE international symposium on Integrated network management V: integrated management in a virtual world: integrated management in a virtual world, p.597–609, 1997.
DUARTE Jr., E. P.; NANYA, T. A hierarchical adaptive distributed system-level diagnosisalgorithm. IEEE Transactions on Computers, v. 47, n. 1, p. 34–45, 1998.
ELNOZAHY, E. N. et al. A survey of rollback-recovery protocols in message-passingsystems. ACM Computing Surveys, v. 34, n. 3, p. 375–408, 2002.
ERIKSSON, H. Mbone: The multicast backbone. Communications of the ACM, v. 37, p.54–60, 1994.
Referencias 86
FAGG, G.; DONGARRA, J. FT-MPI: Fault tolerant MPI. Lecture Notes in ComputerScience: Proceedings of EuroPVM-MPI 2000, 2000.
FIAT, A.; SAIA, J. Censorship resistant peer-to-peer content addressable networks. 13thACM-SIAM Symposium on Discrete Algorithms, p. 94–103, 2002.
FISCHER, M. J.; LYNCH, N. A.; PATERSON, M. S. Impossibility of distributedconsensus with one faulty process. J. ACM, v. 32, n. 2, p. 374–382, 1985.
FOSTER, I. et al. Software infrastructure for the i-way high performance distributedcomputing experiment. 5th IEEE Symposium on High Performance Distributed Computing,p. 562–571, 1997.
FOSTER, I.; KARONIS, N. A grid-enabled MPI: Message passing in heterogeneousdistributed computing systems. SuperComputing 98, p. 1–11, 1998.
FOSTER, I.; KESSELMAN, C. Globus: A metacomputing infrastructure toolkit.International Journal of Supercomputer Applications, v. 11, n. 3, p. 115–128, 1997.
FOSTER, I.; KESSELMAN, C. The Grid: Blueprint for a new Computing Infrastructure.[S.l.]: Morgan Kaufmann, 1998.
FOSTER, I. et al. The physiology of the grid: Open grid services architecture fordistributed systems integration. The Forth Global Grid Forum, 2002.
FOSTER, I.; KESSELMAN, C.; TUECKE, S. The nexus approach to integratingmultithreading and communication. Journal of Parallel and Distributed Computing(JPDC), v. 37, n. 1, p. 70–82, 1996.
FOSTER, I.; KESSELMAN, C.; TUECKE, S. The anatomy of the grid: Enabling scalablevirtual organizations. International Journal of Supercomputer Applications and HighPerformance Computing, p. 81–89, 2001.
FREY, J. et al. Condor-g: A computation management agent for multi-institutional grids.10th IEEE Symposium on High Performance Distributed Computing (HPDC10), p. 83–91,2001.
GENAUD, S.; GIERSCH, A.; VIVIEN, F. Load-balancing scatter operations for gridcomputing. International Parallel and Distributed Processing Symposium (IPDPS 2003),v. 30, n. 8, p. 923–946, 2003.
GLOBAL GRID FORUM. Global Grid Forum. 2005. Http://www.gridforum.org/. Acessoem: dez. 2005.
GRIMSHAW, A. S.; WULF, W. A. The legion vision of a worldwide virtual computer.Communications of the ACM, v. 40, n. 1, p. 39–45, 1997.
GROPP, W. et al. MPICH: A high-performance portable implementation of MPI. ParallelComputing, v. 22, n. 6, p. 789–828, 1996.
HAKIMI, S. L.; AMIN, A. T. Characterization of connection assignments of diagnosablesystems. IEEE Transactions on Computers, v. 23, p. 86–88, 1974.
Referencias 87
HAKIMI, S. L.; NAKAJIMA, K. On adaptive system diagnosis. IEEE Transactions onComputers, v. 33, p. 234–240, 1984.
HAYDEN, M. The Ensemble System. Tese (Doutorado) — Cornel University, Dept.Computer Sciences, 1997.
HOSSEINI, S. H.; KUHL, J. G.; REDDY, S. M. A diagnosis algorithm for distributedcomputing systems with failure and repair. IEEE Transactions on Computers, v. 33, p.223–233, 1984.
IBM WEB SERVICES ARCHITECTURE TEAM. Web services architecture overview.the next stage of evolution for e-business. IBM Technical Document, Web ArchitectureLibrary, 2000.
KARONIS, N.; TOONEN, B.; FOSTER, I. Mpich-g2: A grid-enabled implementation ofthe message passing interface. Journal of Parallel and Distributed Computing (JPDC),v. 63, n. 5, p. 551–563, 2003.
KARONIS, N. T. et al. Exploiting hierarchy in parallel computer networks to optimizecollective operation performance. In International Parallel and Distributed ProcessingSymposium (IPDPS’00), p. 374–384, 2000.
KIELMANN, T. et al. Magpie: MPI collective communication operations for clusteredwide area systems. in ACM SIGPLAN Symposium on Principles and Practice of ParallelProgramming (Ppopp 99), p. 131–140, 1999.
KRULL, J. M.; WU, J.; MOLINA, A. M. Evaluation of a fault-tolerant distributedbroadcast algorithm in hypercube multicomputers. 20th ACM Annual Computer ScienceConference, p. 11–18, 1992.
LITZKOW, M.; LIVNY, M.; MUTKA, M. Condor - a hunter of idle workstations. 8thInternational Conference of Distributed Computing Systems, p. 104–111, 1998.
LITZKOW, M. et al. Checkpoint and migration of unix processes in the condor distributedprocessing system. Technical Report 1346, Universidade de Wisconsin-Madison, 1997.
LOUCA, S. et al. Mpi-ft: Portable fault tolerant scheme for MPI. Parallel ProcessingLetter, v. 10, n. 4, p. 371–382, 1991.
MACDOUGALL, M. H. Simulating computer systems: techniques and tools. [S.l.]: MITPress, 1987. ISBN 0-262-13229-X.
MASSON, G. M.; BLOUGH, D.; SULLIVAN, G. F. Fault-tolerant computer systemdesign. [S.l.]: Prentice-Hall, Inc., 1996. ISBN 0-13-057887-8.
MELLO, S. L. et al. ch hyperbone: Um dispositivo para execucao de programas MPI emhipercubos virtuais. 4o Workshop de Computacao em Grids e Aplicacoes (WCGA), 2006.
MESSAGE PASSING INTERFACE FORUM. MPI: A message-passing interface standard.International Journal of Supercomputer Applications, v. 8, n. 3/4, p. 165–414, 1994.
Referencias 88
MESSAGE PASSING INTERFACE FORUM. MPI-2: Extensions to the message passinginterface. U. Tennessee, 1997.
MPI-POVRAY. Distributed Povray using MPI message passing. 2003.Http://www.verrall.demon.co.uk/mpipov/. Acesso em marco de 2003.
MPIBENCH. MPIbench Home Page. 2005. Http://icl.cs.utk.edu/projects/llcbench/-mpbench.html. Acesso em: dez. 2005.
NORTHEAST PARALLEL ARCHITECTURES CENTER. RSA Factoring by Web. 2005.Http://www.npac.syr.edu/factoring.html. Acesso em: dez. 2005.
OASIS OPEN. Universal Description, Discovery and Integration (UDDI). 2005.Http://www.uddi.org/. Acesso em: dez. 2005.
OURGRID. OurGrid Home Page. 2005. Http://www.ourgrid.org/. Acesso em: dez. 2005.
PLANETLAB. PlanetLab: An Open Plataform for Developing, Deploying, and AccessPlanetary-Scale Services. 2005. Http://www.planet-lab.org. Acesso em: dez. 2005.
PREPARATA, G. M. F.; CHIEN, R. T. On the connection assignment problem ofdiagnosable systems. IEEE Transactions on Electronic Computers, v. 16, p. 848–854,1967.
QBONE. QBone Home Page. 2005. Http://qbone.internet2.edu. Acesso em: dez. 2005.
RANGARAJAN, S.; DAHBURA, A. T.; ZIEGLER, E. A. A distributed system-leveldiagnosis for arbitrary network topologies. IEEE Transactions on Computers, v. 44, p.312–333, 1995.
RATNASAMY, S. et al. A scalable content addressable network. ACM SIGCOMM, p.161–197, 2001.
ROWSTRON, A.; DRUSCHEL, P. Pastry: Scalable distributed object location androuting for large-scale peer-to-peer systems. IFIP/ACM International Conference onDistributed Systems Platforms, p. 329–350, 2001.
SAAD, Y.; SCHULTZ, M. H. Topological properties of hypercube. ACM Transactions onComputers, v. 37, n. 7, p. 867–872, 1998.
SAIA, J. et al. Dynamically fault-tolerant content addressable networks. 1st InternationalWorkshop on Peer-to-Peer Systems (IPTPS ’02), p. 270–279, 2002.
SCHLOSSER, M. et al. Hypercup - hypercubes, ontologies and P2P networks. LectureNotes on Computer Science, v. 2530, p. 112–124, 2002.
SETI INSTITUTE. Home SETI Institute. 2005. Http://www.seti.org/. Acesso em: dez.2005.
SQUYRES, J. M.; LUMSDAINE, A. A component architecture for LAM/MPI. 10thEuropean PVM/MPI Users’ Group Meeting, p. 379–387, 2003.
Referencias 89
STELLNER, G. Cocheck: Checkpointing and process migration for MPI. 10th IEEEInternational Parallel Processing Symposium (IPPS 96), p. 526–531, 1996.
STOICA, I. et al. Chord: A scalable peer-to-peer lookup service for internet application.ACM SIGCOMM, p. 149–160, 2001.
SUPINSKI, B.; KARONIS, N. T. Accurately measuring MPI broadcasts in a computationalgrid. 8th IEEE Symposium on High Performance Distributed Computing, p. 4, 1999.
TIEN, S.-B.; RAGHAVENDRA, C. S. Algorithms and bounds for shortest paths anddiameter in faulty hypercubes. IEEE Transactions on Parallel and Distributed Systems, p.713–718, 1993.
TUECKE, S. et al. Open grid services infrastructure (ogsi) version 1.0. Global Grid ForumDraft Recommendation, 2003.
TUNTAP. Universal TUN/TAP Driver. 2005. Http://vtun.sourceforge.net/tun/. Acessoem: dez. 2005.
UNIVERSITY OF CHICAGO. The Globus Alliance. 2005. Http://www.globus.org.Acesso em: dez. 2005.
UNIVERSITY OF WISCONSIN MADISON. Condor Project Homepage. 2005.Http://www.cs.wisc.edu/condor/. Acesso em: dez. 2005.
WAHL, M.; KILLE, S.; HOWES, T. Lightweight directory access protocol (v3). Requestfor Comments (RFC) 2251, 1997.
WORLD WIDE WEB CONSORTIUM. SOAP Standard. 2005.Http://www.w3.org/TR/soap/. Acesso em: dez. 2005.
WORLD WIDE WEB CONSORTIUM. Web Services Description Language (WSDL).2005. Http://www.w3.org/TR/wsdl. Acesso em: dez. 2005.
WORLD WIDE WEB CONSORTIUM. XML Protocol Working Group. 2005.Http://www.w3c.org/2000/xp/Group/. Acesso em: dez. 2005.
ZHAO, B. Y. et al. Tapestry: a resilient global-scale overlay for service deployment. IEEEJournal on Selected Areas in Communications, v. 2, n. 1, p. 41–53, 2004.
ZHUANG, S. et al. On failure detection algorithms in overlay networks. 24th IEEEInfocom 2005, p. 13–17, 2005.