| Resumo: | Nas últimas três décadas de pesquisa em Sistemas Distribuídos (SDs), um aspecto central discutido é o de sincronia. Com um sistema assíncrono, não fazemos suposições sobre velocidades de execução de processos e / ou atrasos de entrega de mensagens; Com um sistema síncrono, fazemos suposições sobre esses parâmetros [Sch93b]. Sincronismo em SDs impacta diretamente a complexidade e funcionalidade de algoritmos tolerantes a falhas. Uma infra-estrutura síncrona contribui para o desenvolvimento de sistemas mais simples e fiáveis, mas tal infra-estrutura é muito cara e às vezes nem sequer viável de implementar. Uma infra-estrutura totalmente assíncrona é mais realista, mas alguns problemas foram mostrados como insolúveis em tal ambiente através do resultado de impossibilidade por Fischer, Lynch e Paterson [FLP85]. As limitaçes tanto em ambientes totalmente síncronos como totalmente assíncronos levaram ao desenvolvimento de sistemas distribuídos como síncronia parcial [CF99, Ver06]. Em um estudo de funcionalidade de sistemas distribuídos síncronos parciais e de propriedades de Redes Virtuais (RVs), descobrimos que existem vários desafios para este tipo de sistemas que podem ser resolvidos com RVs devido às propriedades que a virtualização traz. Por exemplo a) partilha de recursos fornecida por RVs permite diminuir o custo ao partilhar a parte síncrona da infra-estrutura física, b) isolamento fornecido por a natureza da RVs, isso pode beneficiar os SDs coexistentes na mesma infra-estrutura física que exigem certo nível de isolamento,c) resiliência garantido através do processo de alocação de recursos de Redes Virtuais, isso permite alocar recursos de reposição ao lado dos primários para redes virtuais que exigem garantias de disponibilidade, por exemplo, SDs tolerantes a falhas.Em nosso trabalho, argumentamos que as RVs e um adequado processo de alocação de recursos das RVs oferecem um ambiente adequado para executar aplicativos distribuídos com sincronia parcial. Isto levou à abstração de um novo tipo de RVs: As Redes Virtuais com sincronia híbrida (RVSHs). Nesta tese, apresentamos a idéia geral das Redes Virtuais com sincronia híbrida motivado pelos SDs com síncronia híbrida, e dividimos nosso trabalho em duas partes: a) EspaçoRVSHs propostos pelo SDs com sincronia híbrida em espaço, e b) Tempo-RVSHs propostos pelo SDs com sincronia híbrida em tempo. No SDs com síncronia híbrida em espaço, a infraestrutura é composta de subconjuntos de componentes síncronos e assíncronos, e cada um desses subconjuntos mantém seu status de sincronia através do tempo (i.e., os subconjuntos síncronos permanecem síncronos e os assíncronos permanecem assíncronos). No SDs com síncronia híbrida em tempo, a infra-estrutura é composta de subconjuntos de nós e laços que podem alternar seu status de sincronia através do tempo (i.e., os componentes se comportam de forma síncrona durante os intervalos de tempo e de forma assíncrona durante outros intervalos de tempo). As principais contribuições desta tese são: a) caracterizam os RVSHs em seus dois tipos Espaço-RVSHs e Tempo-RVSHs para refletir tanto a natureza de sincronia em espaço e em tempo; b) propor uma estrutura adequada para o processo de alocação de recursos para ambos Espaço-RVSHs e Tempo-RVSHs, e c) fornecer uma avaliação dos modelos propostos para RVSHs.
In the last three decades of research in Distributed Systems (DSs), one core aspect discussed is the one of synchrony. \Vith an asynchronous system, we make no assumptions about process execution speeds andj or message delivery delays; with a synchronous system, we do make assumptions about these parameters [Sch93b]. Synchrony in DSs impacts directly the complexity and functionality of fault-tolerant algorithms. Although a synchronous infrastructure contributes towards the development of simpler and reliable systems, yet such an infrastructure is too expensive and sometimes even not feasible to implemento On the other hand, a fully asynchronous infrastructure is more realistic, but some problems were shown to be unsolvable in such an environment through the impossibility result by Fischer, Lynch and Paterson [FLP85]. The limitations in both fully synchronous or fully asynchronous environments have led to the development of partial synchronous distributed systems [CF99, Ver06]. In a study of partial synchronous distributed systems functionality, and of Virtual Networks (VNs) properties, we found that there are several challenges for this kind of systems that can be solved with VNs due to the properties that virtualization brings. For example a) resources sharing provided by VNs allows decreasing the cost when sharing the synchronous portion of the physical infrastructure, b) isolation provided by the VNs nature can benefit the coexistent DSs on same physical infrastructure that demand certain leveI of isolation, c) resilience guaranteed through the Virtual Networks Embedding (VNE) process that allows allocating spare resources beside the primary ones for virtual networks that require availability guarantees, for example fault tolerant DSs. In our work, we argue that VNs and a suitable VN embedding process offer suitable environment for running distributed applications with partial synchrony.This has led to the abstraction of new type of VNs: The Hybrid Synchrony Virtual Networks (HSVNs). In this thesis, we introduce the general idea of Hybrid Synchrony Virtual Networks (HSVNs) motivated by the hybrid synchronous DSs, and we branch our work into two branches: a) Space-HSVNs addressed to spatial hybrid synchronous DSs, and b) TimeHSVNs addressed to the time hybrid synchronous DSs. In spatial hybrid synchronous DSs, the hybrid synchronous physical infrastructure is composed of subsets of synchronous and asynchronous components, and each of these subsets maintains its synchrony status through time (i.e., synchronous subsets remain synchronous and asynchronous ones remain asynchronous). In time hybrid synchronous DSs, the hybrid synchronous physical infrastructure is composed of subsets of nodes and links that can alternate their synchrony status through time (i.e., the components behave synchronously during time intervals, and asynchronously during other time intervals). The main contributions of this thesis are: a) characterize the HSVNs in its two types Space-HSVNs and Time-HSVNs to reflect both the synchrony space-variant and time-variant nature ofDSs; b) propose a suitable embedding framework for both Space-HSVNs and TimeHSVNs, and c) provide an evaluation of the embedding mo deIs addressed to the HSVNs. |
