Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T17:39:45Z (GMT). No. of bitstreams: 1 Vignatti_AndreLuis_D.pdf: 822237 bytes, checksum: d9b8ad70708a9313f0d1ed9d64d39302 (MD5) Previous issue date: 2010 / Resumo: Nesta tese, estudamos versões de teoria dos jogos dos problemas de empacotamento de itens e balanceamento de carga. Consideramos que a implementação de um algoritmo centralizado de controle é inviável, fazendo com que as entidades participantes do sistema ajam de maneira egoísta. Assim, a escolha egoísta de estratégias pelas entidades pode ou não levar a um estado estável do sistema, chamado de equilíbrio de Nash. Dependendo das condições definidas pelo modelo utilizado, devemos embutir certas regras para as entidades, contanto que as entidades tenham incentivo de utilizá-las e que, além disso, façam com que o sistema alcance um equilíbrio de Nash. Os principais resultados desta tese são relativos ao tempo de convergência para o equilíbrio de Nash, ou seja, buscamos saber quantas vezes os agentes mudam suas estratégias até alcançarem o equilíbrio de Nash, seja agindo de maneira completamente egoísta ou seguindo certas regras. Para o jogo de empacotamento de itens, apresentamos limitantes teóricos para o tempo de convergência, olhando ambos os casos de atualizações seqüenciais ou simultâneas das estratégias. Para o jogo de balanceamento de carga consideramos um modelo distribuído assíncrono com entidades heterogêneas, apresentando algumas regras que as entidades devem seguir e realizamos simulações para comparar as regras apresentadas / Abstract: In this thesis, we study game-theorical versions of the bin packing and load balancing problems. We consider that the implementation of a centralized controller algorithm is not feasible, making the entities that participate in the system act in a selfish way. Thus, the selfish choice of the strategies by the entities may or may not lead to a stable state of the system, called Nash equilibrium. Depending on the conditions defined by the considered model, we must build certain rules for entities, provided that the entities have incentive to use them and also make the system reach a Nash equilibrium. The main results of this thesis are related to the convergence time to Nash equilibrium, i.e., we seek to know how many times the agents change their strategies until they reach a Nash equilibrium, whether they act in a completely selfish way or follow certain rules. For the bin packing game, we present theoretical bounds for the convergence time, considering both the cases of sequential or simultaneous updates of the strategies. For the load balancing game, we consider an asynchronous distributed model with heterogeneous entities, presenting some rules that the entities must follow and we carry out simulations to compare the presented rules / Doutorado / Teoria da Computação / Doutor em Ciência da Computação

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-01T19:28:54Z No. of bitstreams: 1 TIAGO BRASILEIRO ARAÚJO - DISSERTAÇÃO PPGCC 2016..pdf: 18742851 bytes, checksum: 92b3eefe5e78ab27784255e850871df9 (MD5) / Made available in DSpace on 2018-08-01T19:28:54Z (GMT). No. of bitstreams: 1 TIAGO BRASILEIRO ARAÚJO - DISSERTAÇÃO PPGCC 2016..pdf: 18742851 bytes, checksum: 92b3eefe5e78ab27784255e850871df9 (MD5) Previous issue date: 2016-03-07 / Atualmente, o uso de grandes ontologias em diversos domínios do conhecimento está aumentando. Uma vez que estas ontologias podem apresentar sobreposição de conteúdo, a identificação de correspondências entre seus conceitos se torna necessária. Esse processo é chamado de Matching de Ontologias (MO). Um dos maiores desafios do matching de grandes ontologias é o elevado tempo de execução e o excessivo consumo de recursos de computacionais. Assim, para melhorar a eficiência, técnicas de particionamento de ontologias e paralelismo podem ser empregadas no processo de MO. Este trabalho apresenta uma abordagem para o Matching de Ontologias baseado em Particionamento e Paralelismo (MOPP) que particiona as ontologias de entrada em subontologias e executa as comparações entre conceitos em paralelo, usando o framework MapReduce como solução programável. Embora as técnicas de paralelização possam melhorar a eficiência do processo de MO, essas técnicas apresentam problemas referentes ao desbalanceamento de carga. Por essa razão, o presente trabalho propõe ainda duas técnicas para balanceamento de carga (básica e refinada) para serem aplicadas junto à abordagem MOPP, a fim de orientar a distribuição uniforme das comparações (carga de trabalho) entre os nós de uma infraestrutura computacional. O desempenho da abordagem proposta é avaliado em diferentes cenários (diferentes tamanhos de ontologias e graus de desbalanceamento de carga) utilizando uma infraestrutura computacional e ontologias reais e sintéticas. Os resultados experimentais indicam que a abordagem MOPP é escalável e capaz de reduzir o tempo de execução do processo de MO. No que diz respeito às técnicas de balanceamento de carga, os resultados obtidos mostram que a abordagem MOPP é robusta, mesmo em cenários com elevado grau de desbalanceamento de carga, com a utilização da técnica refinada de balanceamento de carga. / Currently, the use of large ontologies in various áreas of knowledge is increasing. Since, these ontologies can present contents overlap, the identification of correspondences among their concepts is necessary. This process is called Ontologies Matching (OM). One of the major challenges of the large ontologies matching is the high execution time and the computational resources consumption. Therefore, to get the efficiency better, partition and parallel techniques can be employed in the MO process. This work presents a Partition-Parallelbased Ontology Matching (PPOM) approach which partitions the input ontologies in subontologies and executes the comparisons between concepts in parallel, using the framework MapReduce as a programmable solution. Although the parallel techniques can get the MO efficiency process better, these techniques present problems concerning to the load imbalancing. For that reason, our work has proposed two techniques to the load balancing - the basic and the fine-grained one - which are supposed to be applied together with the PPOM approach, in order to orientate the uniform distribution of the comparisons (workload) between the nodes of a computing infrastructure. The performance of the proposed approach is assessed in different settings (different sizes of ontologies and degrees of load imbalancing) using a computing infrastructure and real and synthetic ontologies. The experimental results have indicated that the PPOM approach is scalable and able to reduce the OM process execution time. Referring to the load balancing techniques, the obtained results have shown that the PPOM approach is robust, even in settings with a high load imbalancing, with the fine-grained load balancing technique.

Orientadores: Edmundo Roberto Mauro Madeira, Luiz Eduardo Buzato / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T19:31:37Z (GMT). No. of bitstreams: 1 Nakai_AlanMassaru_D.pdf: 3199160 bytes, checksum: b939ce461412f42df4f371a7cf37d2db (MD5) Previous issue date: 2012 / Resumo: A distribuição de carga é um problema intrínseco a sistemas distribuídos. Esta tese aborda este problema no contexto de servidores web geograficamente distribuídos. A replicação de servidores web em datacenters distribuídos geograficamente provê tolerância a falhas e a possibilidade de fornecer melhores tempos de resposta aos clientes. Uma questão chave em cenários como este é a eficiência da solução de distribuição de carga empregada para dividir a carga do sistema entre as réplicas do servidor. A distribuição de carga permite que os provedores façam melhor uso dos seus recursos, amenizando a necessidade de provisão extra e ajudando a tolerar picos de carga até que o sistema seja ajustado. O objetivo deste trabalho foi estudar e propor novas soluções de distribuição de carga para servidores web geograficamente distribuídos. Para isso, foram implementadas duas ferramentas para apoiar a análise e o desenvolvimento de novas soluções, uma plataforma de testes construída sobre a implementação real de um serviço web e um software de simulação baseado em um modelo realístico de geração de carga para web. As principais contribuições desta tese são as propostas de quatro novas soluções de distribuição de carga que abrangem três diferentes tipos: soluções baseadas em DNS, baseadas em clientes e baseadas em servidores / Abstract: Load balancing is a problem that is intrinsic to distributed systems. In this thesis, we study this problem in the context of geographically distributed web servers. The replication of web servers on geographically distributed datacenters allows the service provider to tolerate failures and to improve the response times perceived by clients. A key issue for achieving good performance in such a deployment is the efficiency of the load balancing solution used to distribute client requests among the replicated servers. The load balancing allows providers to make better use of their resources, soften the need for over-provision, and help tolerate abrupt load peaks until the system can be adjusted. The objective of this work was to study and propose load balancing solutions for geographically distributed web servers. In order to accomplish this objective, we have implemented two tools that support the analysis and development of load balancing solutions, a testbed that was built on top of a real web service implementation and simulation software that is based on a realistic model for web load generation. The main contributions of this thesis are the proposals of four new load balancing solutions that comprehend three types: DNS-based, client-based, and server-based / Doutorado / Ciência da Computação / Doutor em Ciência da Computação