Durant la última dècada, la demanda d’emmagatzematge de dades ha anat creixent exponencialment any rere any. Apart de demanar més capacitat d’emmagatzematge, el usuaris actualment també demanen poder accedir a les seves dades des de qualsevol lloc i des de qualsevol dispositiu. Degut a aquests nous requeriments, els usuaris estan actualment movent les seves dades personals (correus electrònics, documents, fotografies, etc.) cap a serveis d’emmagatzematge en línia com ara Gmail, Facebook, Flickr o Dropbox. Malauradament, aquests serveis d’emmagatzematge en línia estan sostinguts per unes grans infraestructures informàtiques que poques empreses poden finançar. Per tal de reduir el costs d’aquestes grans infraestructures informàtiques, ha sorgit una nova onada de serveis d’emmagatzematge en línia que obtenen grans infraestructures d’emmagatzematge a base d’integrar els recursos petits centres de dades, o fins i tot a base d’integrar els recursos d’emmagatzematge del usuaris finals. No obstant això, els recursos que formen aquestes noves infraestructures d’emmagatzematge són molt heterogenis, cosa que planteja un repte per al dissenyadors d’aquests sistemes: Com es poden dissenyar sistemes d’emmagatzematge en línia, fiables i eficients, quan la infraestructura emprada és tan heterogènia? Aquesta tesis presenta un estudi dels principals problemes que sorgeixen quan un vol respondre a aquesta pregunta. A més proporciona diferents eines per tal d’optimitzar el disseny de sistemes d’emmagatzematge distribuïts i heterogenis. Les principals contribucions són: Primer, creem un marc d’anàlisis per estudiar els efectes de la redundància de dades en el cost dels sistemes d’emmagatzematge distribuïts. Donat un esquema de redundància específic, el marc d’anàlisis presentat permet predir el cost mitjà d’emmagatzematge i el cost mitjà de comunicació d’un sistema d’emmagatzematge implementat sobre qualsevol infraestructura informàtica distribuïda. Segon, analitzem els impactes que la redundància de dades té en la disponibilitat de les dades, i en els temps de recuperació. Donada una redundància, i donat un sistema d’emmagatzematge heterogeni, creem un grup d’algorismes per a determinar la disponibilitat de les dades esperada, i els temps de recuperació esperats. Tercer, dissenyem diferents polítiques d’assignació de dades per a diferents sistemes d’emmagatzematge. Diferenciem entre aquells escenaris on la totalitat de la infraestructura està administrada per una sola organització, i els escenaris on diferents parts auto administrades contribueixen els seus recursos. Els objectius de les nostres polítiques d’assignació de dades són: (i) minimitzar la redundància necessària, (ii) garantir la equitat entre totes les parts que participen al sistema, i (iii) incentivar a les parts perquè contribueixin els seus recursos al sistema. / Over the last decade, users’ storage demands have been growing exponentially year over year. Besides demanding more storage capacity and more data reliability, today users also demand the possibility to access their data from any location and from any device. These new needs encourage users to move their personal data (e.g., E-mails, documents, pictures, etc.) to online storage services such as Gmail, Facebook, Flickr or Dropbox. Unfortunately, these online storage services are built upon expensive large datacenters that only a few big enterprises can afford. To reduce the costs of these large datacenters, a new wave of online storage services has recently emerged integrating storage resources from different small datacenters, or even integrating user storage resources into the provider’s storage infrastructure. However, the storage resources that compose these new storage infrastructures are highly heterogeneous, which poses a challenging problem to storage systems designers: How to design reliable and efficient distributed storage systems over heterogeneous storage infrastructures? This thesis provides an analysis of the main problems that arise when one aims to answer this question. Besides that, this thesis provides different tools to optimize the design of heterogeneous distributed storage systems. The contribution of this thesis is threefold: First, we provide a novel framework to analyze the effects that data redundancy has on the storage and communication costs of distributed storage systems. Given a generic redundancy scheme, the presented framework can predict the average storage costs and the average communication costs of a storage system deployed over a specific storage infrastructure. Second, we analyze the impacts that data redundancy has on data availability and retrieval times. For a given redundancy and a heterogeneous storage infrastructure, we provide a set of algorithms that allow to determine the expected data availability and expected retrieval times. Third, we design different data assignment policies for different storage scenarios. We differentiate between scenarios where the entire storage infrastructure is managed by the same organization, and scenarios where different parties contribute their storage resources. The aims of our assignment policies are: (i) to minimize the required redundancy, (ii) to guarantee fairness among all parties, and (iii) to encourage different parties to contribute their local storage resources to the system.

This thesis shows that abstractions provided by current mainstream Object Oriented (OO) languages are not enough to address the modularization of distributed and concurrent algo- rithms, protocols, or architectures. In particular, we show that code implementing concurrent and distributed algorithms is scattered and tangled in the main implementation of JBoss Cache, a real industrial middleware application. We also show that not only code is tangled, but also conceptual algorithms are hidden behind object-based structures (i.e., they are not visible in the code). Additionally, we show that such code is resilient to modularization. Thus, we show that several cycles of re-engineering (we study the evolution of three different version of JBoss Cache) using the same set of OO abstractions do not improve on the modularization of distributed and concurrent code. From these findings we propose a novel Aspect Oriented programming language with explicit support for distribution and concurrency (AWED). The language uses aspects as main abstractions and propose a model for distributed aspects and remote pointcuts, extending sequential approaches with support for regular sequences of distributed events. The language also proposes advanced support for the manipulation of groups of host, and the fine-grained deterministic ordering of distributed events. To evaluate the proposal we perform several experiments in different domains: refactoring and evolution of replicated caches, development of automatic toll systems, and debugging and testing of distributed applications. Finally, using this general model for distribution we provide two additional contributions. First, we introduce Invasive Patterns, an extension to traditional communication patterns for distributed applications. Invasive Patterns present an aspect-based language to express protocols over distributed topologies considering different coordination strategies (Architec- tural programming). The implementation of this approach is leveraged by the distributed features of AWED and is realized by means of a transformation into it. Second, we add the deterministic manipulation of distributed messages to our model by means of causally ordered protocols.

No description available.

No description available.

No description available.

A possibility of a temporary disconnection of database service exists in many computing environments. It is a common need to permit a participating site to lag behind and re-initialize to full recovery. It is also necessary that active transactions view a globally consistent system state for ongoing operations. We present an algorithm for on-the-fly backup and site-initialization. The technique is non-blocking in the sense that failure and recovery procedures do not interfere with ordinary transactions. As a result the system can tolerate disconnection of services and reconnection of disconnected services, without incurring high overheads

We present an algorithm to store data robustly in a large, geographically distributed network by means of localized regions of data storage that move in response to changing conditions. For example, data might migrate away from failures or toward regions of high demand. The PersistentNode algorithm provides this service robustly, but with limited safety guarantees. We use the RAMBO framework to transform PersistentNode into RamboNode, an algorithm that guarantees atomic consistency in exchange for increased cost and decreased liveness. In addition, a half-life analysis of RamboNode shows that it is robust against continuous low-rate failures. Finally, we provide experimental simulations for the algorithm on 2000 nodes, demonstrating how it services requests and examining how it responds to failures.

Orientador: Aleardo Manacero Junior / Coorientador: Miron Livny / Banca: Sergio Azevedo de Oliveira / Banca: Renata Spolon Lobato / Banca: Alfredo Goldman Lejbman / Banca: Henrique Mongelli / Resumo: Em sistemas distribuídos de larga escala; onde os recursos compartilhados são de propriedade de entidades distintas; existe a necessidade de refletir o fator propriedade dos recursos no processo de escalonamento de tarefas e alocação de recursos. Um sistema de gerenciamento de recursos apropriado deve garantir que os proprietários de recursos tenham acesso aos seus recursos ou ao menos a uma parcela de recursos que seja equivalente a eles. Diferentes políticas podem ser estabelecidas para que o sistema garanta esse direito aos proprietários de recursos; e nessa tese defende-se uma política de escalonamento e alocação de reucrsos chamada Owner-Share Enforcement Policy (OSEP) ou Política de Garantia da Porção do Proprietário; que tem por objetivo garantir o direito de acesso aos recursos através de um sistema de escalonamento baseado em preempção de tarefas e realocação de recursos. Avalia-se a política através da análise de testes e resultados envolvendo métricas de desempenho que descrevem fatores como violação da política; perdada capacidade de processamento; custo da política e satisfação do usuário. Os testes ainda envolveram a análise de desempenho da política em ambientes com a possibilidade de chekcpointing de tarefas; minimizando assim o desperdício de processamento. Fez-se ainda comparações com a política de compartilhamento justo Fair-Share; que permitiram estabelecer as vantagens e desvantagens de cada política e ainda identificar futuros problemas. Por fim; conclui-se a tese identificando as contribuições oferecidas por este trabalho e os trabalhos futuros que podem ser desenvolvidos. / Abstract: In large distributed systems, where shared resources are owned by distinct entities, there is a need to reflect resource ownership in resource allocation. An appropriate resource management system should guarantee that owners of resources have access to their resources or at least to a share of resources proportional to the share of resources they provide. Different policies can be established for guaranteeing the access to resources, and in this thesis we introduce a policy for scheduling and resource allocation named Owner Share Enforcement Policy (OSEP). This policy is based on the concept of distributed ownership and itguarantees the owner's right of accessing their share of resources in a distributed system with a preemptive share space. We evaluate this policy through tests and results analysis involving performance metrics that describe policy violation, loss of capacity, policy cost and user satisfaction. The tests were also conducted in environments withand without job checkpointing, and comparisons with the Fair-Share scheduling policy were made in order to capture the trade-offs of each policy. Finally, we conclude the thesis describing the contributions achieved with this work and pointing directions for future work. / Doutor

The design of a parallel and distributed computing system is a very complicated task. It requires a detailed understanding of the design issues and of the theoretical and practical aspects of their solutions. Firstly, this thesis discusses in detail the major concepts and components required to make parallel and distributed computing a reality. A multithreaded and distributed framework capable of analysing the simulation data produced by a pedestrian simulation software was developed. Secondly, this thesis discusses the origins and fundamentals of Grid computing and the motivations for its use in High Energy Physics. Access to the data produced by the Large Hadron Collider (LHC) has to be provided for more than five thousand scientists all over the world. Users who run analysis jobs on the Grid do not necessarily have expertise in Grid computing. Simple, userfriendly and reliable monitoring of the analysis jobs is one of the key components of the operations of the distributed analysis; reliable monitoring is one of the crucial components of the Worldwide LHC Computing Grid for providing the functionality and performance that is required by the LHC experiments. The CMS Dashboard Task Monitoring and the CMS Dashboard Job Summary monitoring applications were developed to serve the needs of the CMS community.

As autonomous systems develop an ever expanding range of capabilities, monolithic systems (systems with multiple capabilities on a single platform) become increasingly expensive to build and vulnerable to failure. A promising alternative to these monolithic systems is a distributed team with different capabilities that can provide equivalent or greater overall functionality through cooperation. Such systems benefit from decreased individual system cost, robustness to partial system failure, and the possibility of operating over larger geographical areas. However, these benefits come at the cost of increased planning, control, perception, and computational complexity, as well as novel algorithm development. This thesis contributes to the start-of-the-art in distributed systems by drawing on techniques from the fields of formal methods to address problems in team task and motion planning, and from computer vision to address problems in multi-robot perception (specifically multi-image feature matching). These problems arise in persistent surveillance, robotic agriculture, post-disaster search and rescue, and autonomous driving applications. Overall, this work enables resilient hierarchical planning for robot teams and solves the distributed multi-image feature matching problem, both of which were previously intractable to solve in many cases. We begin by exploring distributed multi-image feature matching for distributed perception and object tracking for a robot team or camera network. We then look at homogeneous multi-agent planning from rich infinite-time specifications that includes a secondary objective of optimizing local sensor information entropy. Next, we address heterogeneous multi-agent task planning from rich, timed specifications based on agent capabilities, and then detail mechanisms for online replanning due to agent loss. Finally, we address safe, reactive, and timed motion planning subject to temporal logic constraints. Accompanying each topic are a number of simulations and experiments that demonstrate their utility on real hardware. Overall, this thesis focuses on four primary contributions: 1) distributed multi-image feature matching, 2) motion planning for a homogeneous robotic team subject to distributed sensing and temporal logic constraints, 3) task planning for a heterogeneous robotic team with reactivity to changing agent availability, and 4) safe motion planning for an individual system that is reactive to disturbances and satisfies timed temporal logic constraints. / 2022-09-30T00:00:00Z