Em diversas instituições universitárias existem centenas ou milhares de computadores que costumam ser subutilizados. Esses computadores não apresentam toda sua capacidade processamento aproveitada, ficando em grande parte do tempo em estado ocioso ou até mesmo desligados. Frequentemente, grupos de pesquisas dessas mesmas instituições possuem aplicações que necessitam de um grande poder de processamento. A fim de suprir essa necessidade esses grupos acabam tendo de investir na aquisição de computadores de grande porte ou clusters de computadores. Muitas dessas aplicações são do tipo Bag-of-Tasks, isto é, são praticamente independentes, não havendo necessidade de comunicação entre as tarefas. Desta forma, poderiam ser executadas perfeitamente em um ambiente de grade, que pode ser construído a partir de recursos ociosos já existentes nessas instituições. Dentro deste enfoque, decidiu-se pela construção de uma grade institucional na Universidade de Caxias do Sul (UCS). Essa grade foi utilizada para a realização de simulações computacionais de materiais (clatratos de carbono e sacarose). Diversas fases hipotéticas do carbono tiveram suas propriedades calculadas por meio de simulações computacionais, em distintas aproximações. No entanto, em geral não há na literatura simulações computacionais de boa qualidade dos espectros vibracionais (Raman e de absorção no infravermelho) destas fases de carbono, o que torna essencialmente impossível sua identificação em amostras reais. A disponibilidade de melhores recursos de hardware/software e novos funcionais de troca e correlação (e a eventual inclusão de interações do tipo van der Waals), bem como a possibilidade do cálculo do espectro vibracional, constituem elementos que poderão contribuir significativamente para estabelecer uma ponte entre os resultados das simulações computacionais e resultados experimentais obtidos com amostras reais. O cálculo ab initio sistemático das propriedades físicas de diferentes fases reais e hipotéticas do carbono, poderá inclusive guiar a realização de experimentos visando a síntese das fases mais promissoras do ponto de vista de suas propriedades. Foram estudados neste trabalho os clatratos C46 e Li8C46 e a sacarose. Os clatratos são materiais com propriedades físicas de grande potencial para a realização de aplicações tecnológicas. Esses clatratos de carbono, até este trabalho, não tiveram suas rotas de síntese estabelecidas. Neste trabalho foi feita a otimização da estrutura e o cálculo do espectro vibracional dos clatratos C46 e Li8C46. A previsão dos espectros de Raman e infravermelho pode auxiliar na descoberta desses materiais. No estudo das propriedades vibracionais do clatrato Li8C46 foi observada a necessidade da revisão de resultados encontrados na literatura. Para a sacarose foram comparados os resultados de simulação computacional realizados neste trabalho com resultados experimentais já disponíveis sobre o efeito de altas pressões (até 14 GPa) sobre os modos vibracionais deste composto. Foi observado um aumento nas frequências com o aumento da pressão, para os modos associados a vibrações CH, CO e CC, conforme o esperado. Por outro lado, a banda associada ao OH não-ligado da sacarose deslocou-se para frequências mais baixas, indicando a formação de uma ligação de hidrogênio induzida por pressão. O comportamento geral do espectro de infravermelho sob pressão foi completamente reversível com a diminuição da pressão, revelando a estabilidade da sacarose até 14 GPa, em condições quase hidrostáticas. / In many universities there are hundreds or thousands of computers whose computational power is not fully utilized. These computers use to stay idle or even turned off most of the time. Often, the research groups of these institutions deal with applications that require lots of processing power. With the intent of solving this need, these groups end up buying high performance computers or computer clusters. Many of these applications are Bag-of- Tasks applications, that is, they are almost independent and have no need to communicate with each other. This makes it possible for the applications to run without problems in a computational grid. Such environment can be built using the available resources at those institutions. Within this approach it was decided to build/develop an institutional computer grid in the Universidade de Caxias do Sul (UCS). This grid has been used to run computer simulations of materials(carbon clathrate and sucrose). Various hypotetical carbon structures had their properties calculated by means of computer simulations using different approaches. However, there are no good quality simulation in literature for vibrational spectra (Raman and infrared absorbance) the computer simulations for those carbon structures, which makes their identification essentially impossible in real samples. The availability of better hardware/software resources and the new exchange-correlation functionals (and the possible inclusion of van der Waals interactions), as well as the possibility of calculating the vibrational spectra, constitute elements that may contribute significantly to establish a bridge between the results of computer simulations and the experimental results obtained from real samples. The systematic ab initio calculation of the physical properties from different real and hypotetic carbon stages may guide the execution of experiments for the synthesis of the most promissing stages from the point of view of its properties. The carbon clathrates C46 and Li8C46, along with sacarose, were subjected to study in this work. The clathrates are materials with physical properties of great potential for technologial applications. Those carbon clathrates, until this work, did not have their synthesis routes established. In the present work the structure optimization and the calculation of the C46 and Li8C46 clathrates vibrational spectrums was done. The prediction from the Raman spectrums and infrared can help in the discovery of these materials. In the study of the vibrational properties of Li8C46 clathrate, it has been observed the need to review the results found in literature. For sucrose the results of computational simulation found on this work were compared to the experimental results already available for the effect of high pressure (up to 14 GPa) on the vibrational modes. It has been observed an increase in the frequency with increasing pressure for the bands assigned to the modes CH, CO and CC, as expected. On the other hand, the band associated to the non-bonded OH from the sucrose has shifted to lower frequencies, indication the formation of a hydrogen pressured induced bond. The general behaviour of the infrared spectra under pressure was completly reversible upon pressure release, revealing the stability of sucrose up to 14 GPa, in nearly hydrostatic conditions.

Um dado por si só não possui valor algum, a menos que ele seja interpretado, contextualizado e agregado com outros dados, para então possuir valor, tornando-o uma informação. Em algumas classes de aplicações o valor não está apenas na informação, mas também na velocidade com que essa informação é obtida. As negociações de alta frequência (NAF) são um bom exemplo onde a lucratividade é diretamente proporcional a latência (LOVELESS; STOIKOV; WAEBER, 2013). Com a evolução do hardware e de ferramentas de processamento de dados diversas aplicações que antes levavam horas para produzir resultados, hoje precisam produzir resultados em questão de minutos ou segundos (BARLOW, 2013). Este tipo de aplicação tem como característica, além da necessidade de processamento em tempo-real ou quase real, a ingestão contínua de grandes e ilimitadas quantidades de dados na forma de tuplas ou eventos. A crescente demanda por aplicações com esses requisitos levou a criação de sistemas que disponibilizam um modelo de programação que abstrai detalhes como escalonamento, tolerância a falhas, processamento e otimização de consultas. Estes sistemas são conhecidos como Stream Processing Systems (SPS), Data Stream Management Systems (DSMS) (CHAKRAVARTHY, 2009) ou Stream Processing Engines (SPE) (ABADI et al., 2005). Ultimamente estes sistemas adotaram uma arquitetura distribuída como forma de lidar com as quantidades cada vez maiores de dados (ZAHARIA et al., 2012). Entre estes sistemas estão S4, Storm, Spark Streaming, Flink Streaming e mais recentemente Samza e Apache Beam. Estes sistemas modelam o processamento de dados através de um grafo de fluxo com vértices representando os operadores e as arestas representando os data streams. Mas as similaridades não vão muito além disso, pois cada sistema possui suas particularidades com relação aos mecanismos de tolerância e recuperação a falhas, escalonamento e paralelismo de operadores, e padrões de comunicação. Neste senário seria útil possuir uma ferramenta para a comparação destes sistemas em diferentes workloads, para auxiliar na seleção da plataforma mais adequada para um trabalho específico. Este trabalho propõe um benchmark composto por aplicações de diferentes áreas, bem como um framework para o desenvolvimento e avaliação de SPSs distribuídos. / Recently a new application domain characterized by the continuous and low-latency processing of large volumes of data has been gaining attention. The growing number of applications of such genre has led to the creation of Stream Processing Systems (SPSs), systems that abstract the details of real-time applications from the developer. More recently, the ever increasing volumes of data to be processed gave rise to distributed SPSs. Currently there are in the market several distributed SPSs, however the existing benchmarks designed for the evaluation this kind of system covers only a few applications and workloads, while these systems have a much wider set of applications. In this work a benchmark for stream processing systems is proposed. Based on a survey of several papers with real-time and stream applications, the most used applications and areas were outlined, as well as the most used metrics in the performance evaluation of such applications. With these information the metrics of the benchmark were selected as well as a list of possible application to be part of the benchmark. Those passed through a workload characterization in order to select a diverse set of applications. To ease the evaluation of SPSs a framework was created with an API to generalize the application development and collect metrics, with the possibility of extending it to support other platforms in the future. To prove the usefulness of the benchmark, a subset of the applications were executed on Storm and Spark using the Azure Platform and the results have demonstrated the usefulness of the benchmark suite in comparing these systems.

Devido ao contínuo crescimento dos dados científicos nos últimos anos, a análise intensiva de dados nessas quantidades massivas de dados é muito importante para extrair informações valiosas. Por outro lado, o formato de dados científicos GRIB (GRIdded Binary) é amplamente utilizado na comunidade meteorológica para armazenar histórico de dados e previsões meteorológicas. No entanto, as ferramentas atuais disponíveis e métodos para processar arquivos neste formato não realizam o processamento em um ambiente distribuído. Essa situação limita as capacidades de análise dos cientistas que precisam realizar uma avaliação sobre grandes conjuntos de dados com o objetivo de obter informação no menor tempo possível fazendo uso de todos os recursos disponíveis. Neste contexto, este trabalho apresenta uma alternativa ao processamento de dados no formato GRIB usando o padrão Manager-Worker implementado com o modelo de atores fornecido pelo Akka toolkit. Realizamos também uma comparação da nossa proposta com outros mecanismos, como o round-robin, random, balanceamento de carga adaptativo, bem como com um dos principais frameworks para o processamento de grandes quantidades de dados tal como o Apache Spark. A metodologia utilizada considera vários fatores para avaliar o processamento dos arquivos GRIB. Os experimentos foram conduzidos em um cluster na plataforma Microsoft Azure. Os resultados mostram que nossa proposta escala bem à medida que o número de nós aumenta. Assim, nossa proposta atingiu um melhor desempenho em relação aos outros mecanismos utilizados para a comparação, particularmente quando foram utilizadas oito máquinas virtuais para executar as tarefas. Nosso trabalho com o uso de metadados alcançou um ganho de 53.88%, 62.42%, 62.97%, 61.92%, 62.44% e 59.36% em relação aos mecanismos round-robin, random, balanceamento de carga adaptativo que usou métricas CPU, JVM Heap e um combinado de métricas, e o Apache Spark, respectivamente, em um cenário onde um critério de busca é aplicado para selecionar 2 dos 27 parâmetros totais encontrados no conjunto de dados utilizado nos experimentos. / Because of the continuous and overwhelming growth of scientific data in the last few years, data-intensive analysis on this vast amount of scientific data is very important to extract valuable scientific information. The GRIB (GRIdded Binary) scientific data format is widely used within the meteorological community and is used to store historical meteorological data and weather forecast simulation results. However, current libraries to process the GRIB files do not perform the computation in a distributed environment. This situation limits the analytical capabilities of scientists who need to perform analysis on large data sets in order to obtain information in the shortest time possible using of all available resources. In this context, this work presents an alternative to data processing in the GRIB format using the well-know Manager-Worker pattern, which was implemented with the Actor model provided by the Akka toolkit. We also compare our proposal with other mechanisms, such as the round-robin, random and an adaptive load balancing, as well as with one of the main frameworks currently existing for big data processing, Apache Spark. The methodology used considers several factors to evaluate the processing of the GRIB files. The experiments were conducted on a cluster in Microsoft Azure platform. The results show that our proposal scales well as the number of worker nodes increases. Our work reached a better performance in relation to the other mechanisms used for the comparison particularly when eight worker virtual machines were used. Thus, our proposal upon using metadata achieved a gain of 53.88%, 62.42%, 62.97%, 61.92%, 62.44% and 59.36% in relation to the mechanisms: round-robin, random, an adaptive load balancing that used CPU, JVM Heap and mix metrics, and the Apache Spark respectively, in a scenario where a search criteria is applied to select 2 of 27 total parameters found in the dataset used in the experiments.

Nos últimos anos, Cloud Computing tem se tornado uma tecnologia importante que possibilitou executar aplicações sem a necessidade de implementar uma infraestrutura física com a vantagem de reduzir os custos ao usuário cobrando somente pelos recursos computacionais utilizados pela aplicação. O desafio com a implementação de aplicações distribuídas em ambientes de Cloud Computing é o planejamento da infraestrutura de máquinas virtuais visando otimizar o tempo de execução e o custo da implementação. Assim mesmo, nos últimos anos temos visto como a quantidade de dados produzida pelas aplicações cresceu mais que nunca. Estes dados contêm informação valiosa que deve ser obtida utilizando ferramentas como MapReduce. MapReduce é um importante framework para análise de grandes quantidades de dados desde que foi proposto pela Google, e disponibilizado Open Source pela Apache com a sua implementação Hadoop. O objetivo deste trabalho é apresentar que é possível predizer o tempo de execução de uma aplicação distribuída, a saber, uma aplicação MapReduce, na infraestrutura de Cloud Computing, utilizando um modelo matemático baseado em especificações teóricas. Após medir o tempo levado na execução da aplicação e variando os parámetros indicados no modelo matemático, e, após utilizar uma técnica de regressão linear, o objetivo é atingido encontrando um modelo do tempo de execução que foi posteriormente aplicado para predizer o tempo de execução de aplicações MapReduce com resultados satisfatórios. Os experimentos foram realizados em diferentes configurações: a saber, executando diferentes aplicações MapReduce em clusters privados e públicos, bem como em infraestruturas de Cloud comercial, e variando o número de nós que compõem o cluster, e o tamanho do workload dado à aplicação. Os experimentos mostraram uma clara relação com o modelo teórico, indicando que o modelo é, de fato, capaz de predizer o tempo de execução de aplicações MapReduce. O modelo desenvolvido é genérico, o que quer dizer que utiliza abstrações teóricas para a capacidade computacional do ambiente e o custo computacional da aplicação MapReduce. Motiva-se a desenvolver trabalhos futuros para estender esta abordagem para atingir outro tipo de aplicações distribuídas, e também incluir o modelo matemático deste trabalho dentro de serviços na núvem que ofereçam plataformas MapReduce, a fim de ajudar os usuários a planejar suas implementações. / In the last years, Cloud Computing has become a key technology that made possible running applications without needing to deploy a physical infrastructure with the advantage of lowering costs to the user by charging only for the computational resources used by the application. The challenge with deploying distributed applications in Cloud Computing environments is that the virtual machine infrastructure should be planned in a way that is time and cost-effective. Also, in the last years we have seen how the amount of data produced by applications has grown bigger than ever. This data contains valuable information that has to be extracted using tools like MapReduce. MapReduce is an important framework to analyze large amounts of data since it was proposed by Google, and made open source by Apache with its Hadoop implementation. The goal of this work is to show that the execution time of a distributed application, namely, a MapReduce application, in a Cloud computing environment, can be predicted using a mathematical model based on theoretical specifications. This prediction is made to help the users of the Cloud Computing environment to plan their deployments, i.e., quantify the number of virtual machines and its characteristics in order to have a lesser cost and/or time. After measuring the application execution time and varying parameters stated in the mathematical model, and after that, using a linear regression technique, the goal is achieved finding a model of the execution time which was then applied to predict the execution time of MapReduce applications with satisfying results. The experiments were conducted in several configurations: namely, private and public clusters, as well as commercial cloud infrastructures, running different MapReduce applications, and varying the number of nodes composing the cluster, as well as the amount of workload given to the application. Experiments showed a clear relation with the theoretical model, revealing that the model is in fact able to predict the execution time of MapReduce applications. The developed model is generic, meaning that it uses theoretical abstractions for the computing capacity of the environment and the computing cost of the MapReduce application. Further work in extending this approach to fit other types of distributed applications is encouraged, as well as including this mathematical model into Cloud services offering MapReduce platforms, in order to aid users plan their deployments.

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-18T19:59:40Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-09T01:30:39Z : No. of bitstreams: 1 147062.pdf: 26990741 bytes, checksum: ca8899dbcf6d7cbdee886121bd4811b6 (MD5)

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-19T06:11:03Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-26T00:13:12Z : No. of bitstreams: 1 184240.pdf: 8766965 bytes, checksum: 4d89f96d03ccb310e3adeea31f3b84ab (MD5) / Esta dissertação tem como objetivo a análise do Processamento de Consultas em Banco de Dados para Aplicações Avançadas, assim como, realizar um comparativo entre elas. Foram abordadas as seguintes tecnologias de Banco de Dados: Centralizado, Distribuído, Orientado a Objeto, Relacional-Objeto, Móveis e Multimídia. Cada aplicação de Banco de Dados pesquisada nesta dissertação busca atender uma necessidade de mercado. Devido `s particularidades das aplicações do banco de dados, observa-se que o processamento de consultas possui aspectos relevantes que são tratados diferencialmente em cada aplicação. No decorrer do trabalho foram relatadas algumas características, pontos relevantes e restrições de cada Banco de Dados, ressaltando sempre o processamento de consultas e suas etapas, principalmente a otimização. Para concluir a pesquisa foram realizados estudos comparativos entre as diversas aplicações abordadas, enfatizando seus principais aspectos.

Este trabalho analisa o uso de redes de estações de trabalho como uma única máquina a ser utilizada para permitir o processamento de problemas que não poderiam ser computados, aceitavelmente, em apenas um de seus nodos, seja por causa do tempo dispendido ou de recursos físicos necessários, como memória principal. São enfocados dois algoritmos de redes neurais artificiais - Combinatorial Neural Model e Back Propagation - que apresentam os problemas enunciados acima, e uma proposta de um esquema para distribuição dessa classe de algoritmos, levando em consideração as vantagens disponíveis no ambiente em questão, a apresentada. A implementação do modelo proposto, sob a forma de um simulador distribuído baseado no conceito de servidor está descrita no trabalho, assim como as estratégias de paralelização dos algoritmos. Ao final, são apresentados os resultados obtidos, quantitativa e qualitativamente, e uma avaliação mais detalhada da paralelização do algoritmo Back Propagation a exposta. / The use of workstation networks as distributed multicomputers to solve resource demanding problems that cannot be feasibly solved in one node is the main concern of this work. Two different artificial neural network algorithms, Combinatorial Neural Model and Back Propagation, are faced and a scheme for distributing this class of algorithms is presented. The several advantages of the environment are focused in the proposal along with its disadvantages. This work also presents the implementation of the proposed scheme allowing an in loco performance evaluation. At the end results are shown and a more in depth evaluation of the Back Propagation parallelization is presented.

Linguagens de programação orientadas a objetos possuem diversas características que facilitam sua utilização frente a outras linguagens imperativas. No projeto e desenvolvimento de software, o mecanismo de herança permite a construção de sistemas na forma incremental e evolutiva, possibilitando a reutilização de códigos já escritos. Também a possível atingir aplicações com bons níveis de segurança e confiabilidade, através do encapsulamento de dados e funções sob forma de objetos, que também representam a unidade básica de execução em uma linguagem orientada a objetos. O mesmo recurso que possibilita níveis elevados de segurança permite que linguagens orientadas a objetos sejam inerentemente distribuídas. Objetos possuem tanto área de dados e código de execução independentes dos demais. Acessos aos dados internos de um objeto somente são possíveis através de mensagens explicitas entre objetos. Neste caso um objeto solicita uma ação específica a outro objeto, podendo ser enviados parâmetros e existir retorno de resultados. Este trabalho apresenta um modelo para construção de uma linguagem orientada a objetos distribuída. O ambiente para suportar a execução ao modelo é compostos por vários nodos de processamento com memórias locais individuais e contando com uma rede de comunicação para troca de mensagens entre os nodos. O modelo e discutido em dois níveis distintos: a nível de linguagem e a nível operacional. A nível de linguagem são analisados os recursos de programação normalmente utilizados em linguagens orientadas a objetos quando implementados em ambientes distribuídos. O ambiente de suporte A execução necessário ao suporte do modelo da linguagem a analisado pelo nível operacional. A apresentação do modelo a nível de linguagem discute as características de uma linguagem orientada a objetos distribuída frente as implementações seqüenciais convencionais. E ressaltada a implementado de herança em um ambiente de execução distribuído, que, não podendo ser através de compartilhamento, é efetuada através de copia de código. Também são apresentadas novas diretivas de compilação necessárias exclusivamente a ambientes distribuídos. Tais diretivas visam explorar níveis de concorrência de uma aplicação durante sua execução, diferenciando classes que definem objetos locais ou distribuídos e diferentes tipos de mensagens entre objetos. As formas de extrair o melhor desempenho nas aplicações e o gerenciamento do ambiente de execução são os pontos abordados pelo nível operacional do modelo. Em operação neste nível, um elemento de gerencia de execução permite o controle tanto dos objetos da aplicação quanto dos nodos de processamento disponíveis para execução. A tarefa de controle de objetos viabiliza a criação e remoção de objetos durante a execução da aplicação, bem como a identificação de localização destes. O controle dos nodos de processamento possibilita analisar continuamente a carga computacional dos nodos de processamento. Assim, cada objeto a ser criado pode ser alocado em um nodo onde a carga computacional esteja baixa, propiciando um melhor desempenho no momento de execução da aplicação distribuído a carga entre os nodos. A unido do modelo de execução distribuído proposto a uma linguagem orientada a objetos resulta em uma linguagem eficiente tanto na produção de software como no desempenho de aplicações. A eficiência na produção de sistemas 6 obtida através de dois itens, a utilização do paradigma de orientação a objetos e a transparência do nível operacional para o programador, que não necessita conhecer os mecanismos utilizados para ativação de objetos e envio de mensagens. A eficiência de execução é obtida através da utilização de múltiplos nodos processadores servindo como base a execução. Neste trabalho é também apresentado um protótipo para uma linguagem suportando o modelo distribuído proposto. A linguagem, denominada DPC++ (Processamento Distribuído em C++), é voltada para execução em redes de estações de trabalho, sobre o sistema operacional Unix, utilizando sockets como mecanismo de comunicação. O estilo de programação em DPC++ é baseado em C++. / The objects-oriented programming languages have many features who make simple their use in front of others imperatives languages. In the software project and development, the inheritance mechanism allows an increasing and evaluative way of codes that have been written. It also possible gain applications with goods levels of security and confiability with the encapsulation of both data and functions in the form of object, which represent the basic execution unit in an object-oriented language. The same resource that provides high levels of security also permits that object-oriented languages may be inherently distributed. Objects have their own area of data, their execution codes are independent from the other. Accesses to the internal data of an object are possible only through a specific protocol among objets. When this occurs, an object requests a specific action to other object with or without parameters or results return. This work presents a model for build a distributed object-oriented language, devoted to environments compounded by several processing nodes with local memory and linked by a communication network. The model is discussed in two different levels: language level and operational level. In the language level are analyzed the programming resources usually used in object-oriented languages when implemented in distributed environments. The executing environments support are analyzed in the operational level. In the language level presentation are made a discussion about distributed object-oriented language features in front of conventional sequential implementations. It is emphasized inheritance in a distributed executing environment, who is done by code copy, due to can not be by memory sharing. Also are presented news compilation directives necessaries to the distributed environment. Those directives aim to explorer concurrence levels in an application during its execution, differing class who defining local or distributed objects and the different messages types among objects. The operational level boards the ways that mean to extract the best performance for the applications and the execution environment management. An execution manager element allows the control as the application objects as the available to execution processor nodes. The task of object control makes possible the objects creation and removal during the application executing as well their network identification. The processor nodes control allows the continuous analyzes of the computational load in the nodes available to processing. In this way, every object to be created can be allocated in a node with low occupation rates, propitiating a better performance in the application executing. The union of the proposed distributed execution model to an objectoriented language results in an efficient language as in the software production as in execution performance. The systems production efficiency is obtained from two items: the utilization of the object-oriented paradigm an the transparency of the operational level to the programmer, that no need know the used mechanisms to object activation and message exchange. The execution efficiency is gained by the utilization of multiples processor nodes supporting the application executing. In this work is presented a prototype that implements the proposed model. The language, called DPC++, Distributed Processing in C++, is turned to execute in workstation network with Unix operational system, using sockets as communication mechanism. The style of DPC++ programming are based in C++.

Orientador: Elias Procópio Duarte Jr / Dissertação (mestrado) - Universidade Federal do Paraná / Resumo: Neste trabalho é apresentado um novo algoritmo para o diagnóstico distribuído de redes de topologia arbitrária baseado no algoritmo do Carteiro Chinês. Um agente móvel, isto é, um processo que é executado e transmitido entre os nodos da rede, percorre seqüencialmente todos os enlaces, de acordo com o caminho determinado pelo algoritmo do Carteiro Chinês. O agente, chamado Agente Chinês, vai testando os enlaces detectando novos eventos e disseminando as informações obtidas para os demais nodos da rede. Quando todos os nodos do sistema recebem a informação sobre um evento, o diagnóstico se completa. Neste trabalho assume-se que falhas não particionam a rede, e que um novo evento só ocorre após o diagnóstico do evento anterior. São apresentadas provas rigorosas do melhor e pior caso da latência do algoritmo, isto é, o tempo necessário para completar um diagnóstico. São apresentados também resultados experimentais obtidos através da simulação do algoritmo em vários tipos diferentes de topologia, dentre eles, hipercubos de 16, 64 e 128 vértices, grafo D 1,2 com 9 vértices, além de um grafo randômico com 50 vértices e probabilidade de aresta igual a 10%, e a topologia da Rede Nacional de Pesquisa (RNP). São simuladas falhas de um enlace em cada grafo, são medidos o número de mensagens geradas e o tempo necessário para que o diagnóstico se complete. Os resultados indicam que o tempo necessário para realizar o diagnóstico é, na média, menor que o pior caso apresentado, e que o número de mensagens disseminadas é freqüentemente menor que o requerido por outros algoritmos semelhantes. / Abstract: This work presents a new algorithm for distributed diagnosis of general topology networks. A mobile agent visits all links sequentially, following the path generated by the Chinese Postman algorithm. The agent, called Chinese Agent, tests the links detecting new events and disseminates event information to the rest of the network. When all nodes of the system receive the information about the event, the diagnosis is complete. This work assumes that faults do not partition the network, and that a new event only occurs after the previous event has been diagnosed. Rigorous proofs of the best and the worst case of the latency of the algorithm are presented. Experimental results are also presented which were obtained from the simulation of the algorithm on different types of topologies, like hypercubes with 16, 64 and 128 nodes, the D 1,2 graph with 9 nodes, a random graph with 50 nodes and link probability equal to 10%, and the Brazilian National Research Network (RNP) topology. One link fault is simulated in each graph, both the number of messages and the algorithm's latency were measured. The results show that the time necessary to complete the diagnosis is, in average, smaller than the worst case. A comparison with other algorithms shows that the number of messages generated by the proposed algorithm is frequently smaller than the number of messages required by others similar algorithms.

No description available.