XML tornou-se um padrÃo amplamente utilizado na representaÃÃo e troca de dados entre aplicaÃÃes na Web. Com isso, um grande volume desses dados està distribuÃdo na Web e armazenado em diversos meios de persistÃncia. SGBDs relacionais que suportam XML fornecem tÃcnicas de controle de concorrÃncia para gerenciar esses dados. No entanto, a estrutura de dados XML dificulta a aplicaÃÃo dessas tÃcnicas. Adicionalmente, as tÃcnicas de replicaÃÃo tÃm sido utilizadas para melhorar o gerenciamento de grandes quantidades de dados XML. Pesquisas atuais de replicaÃÃo de dados XML consistem em adaptar os conceitos existentes ao modelo semi-estruturado. Em especial, a replicaÃÃo total apresenta uma grande quantidade de bloqueios, em decorrÃncia das atualizaÃÃes ocorrerem em todas as cÃpias da base. Por outro lado, a replicaÃÃo parcial visa aumentar a concorrÃncia entre as transaÃÃes, com uma menor quantidade de bloqueios em relaÃÃo à replicaÃÃo total. Este trabalho apresenta o RepliXP, uma estratÃgia para o gerenciamento da replicaÃÃo parcial de dados XML. Ele à apresentado como um mecanismo que combina caracterÃsticas de protocolos de replicaÃÃo sÃncronos e assÃncronos para diminuir o nÃmero de bloqueios de atualizaÃÃo. Para validar a estratÃgia, foram realizados testes de desempenho analisando o tempo de resposta das transaÃÃes. Foram comparadas as abordagens de replicaÃÃo total e replicaÃÃo parcial no RepliXP. De acordo com os resultados obtidos, o RepliXP utilizando a estratÃgia de replicaÃÃo parcial de dados XML proporcionou uma melhoria no tempo de resposta das transaÃÃes concorrentes. / XML has become a widely used standard in representing and exchanging data among Web Applications. Consequently, a large amount of data is distributed on the Web and stored in several persistence medias. Relational DBMSs XML-enabled provide concurrency control techniques to manage such data. However, XML data structure makes it difficult implementation of these techniques. Additionally, replication techniques have been used to improve management of large amounts of XML data. Current researches of XML data replication consist of to adapt existing concepts to semi-structured model. In particular, full replication provides a large of locks, due to updates that have occurred on all copies of the base. Moreover, the partial replication aims to increase concurrency among transactions, with a smaller amount of blocks in relation to total replication. This work presents the RepliXP, towards for management of partial replication of XML data. It is presented as a mechanism that combines features of synchronous and asynchronous replication protocols to reduce the amount of update locks. In order to evaluate the strategy, performance tests were carried out by analyzing the response time of transactions. Full and partial replication approaches were compared in RepliXP. According to the results, RepliXP using the strategy of partial XML data replication provided an improvement in response time of concurrent transactions.

Autômatos não-seqüenciais constituem um domínio semântico categorial do tipo não-intercalação para sistemas reativos, comunicantes e concorrentes.É baseado em sistemas de transições etiquetados, inspirado em "Redes de Petri são Monóides" de Meseguer e Montanari, onde as operações de sincronização e encapsulação são funtoriais e as reificações constituem uma classe de morfismos especiais. Do que se tem conhecimento, é o primeiro modelo de concorrência a satisfazer a composicionalidade diagonal, ou seja, onde as reificações compõem (verticalmente) e distribuem-se sobre a composição paralela (verticalmente). Adjunções entre autômatos não-seqüenciais, redes de Petri e autômatos seqüenciais são introduzidas estendendo a abordagem de Winskel, Nielsen e Sassone onde é proposta uma classificação formal para modelos de concorrência. Dos passos que envolvem a passagem de um modelo para outro, pode-se inferir que os autômatos não-seqüenciais são mais concretos do que as redes de Petri e os autômatos seqüenciais. Para experimentar o domínio semântico proposto, é dada semântica a uma linguagem concorrente, baseada nos objetos, denominada Náutilus. Trata-se de uma versão simplificada e revisada da linguagem de especificação orientada aos objetos GNOME, onde são introduzidos algumas facilidades especiais, inspiradas no domínio semântico, como a reificação e a agregação. Neste contexto, a composicionalidade diagonal é uma propriedade essencial para dar a semântica. / Nonsequential automata constitute a non-interleaving categorial semantic domain for reactive, communicating and concurrent systems. It is based on labeled transition systems, inspired by Meseguer and Montanari's "Petri Nets are Monoids", where synchronization and encapsulation operations are functorial and a class of morphisms stands for reification. It is, for our knowledge, the first model for concurrency which satisfies the diagonal compositionality requirement, i. e., reifications compose (vertical) and distribute over the parallel composition (horizontal). Adjunctions between nonsequential automata, Petri nets and sequential automata are provided extending the approach of Winskel, Nielsen and Sassone where a scene for a formal classification of models for concurrency is set. The steps of abstraction involved in moving between models show that nonsequential automata are more concrete than Petri nets and sequential automata. To experiment with the proposed semantic domain, a semantics for a concurrent, object-based language named Nautilus is given. It is a simplified and revised version of the object-oriented specification language GNOME, introducing some special features inspired by the semantic domain such as reification and aggregation. The diagonal compositionality is an essential property to give semantics in this context.

Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-09T13:43:25Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Francisco Miranda Soares da Silva Neto.pdf: 1968720 bytes, checksum: 60383d7751d95b545cae9a16a83f611c (MD5) / Made available in DSpace on 2015-03-09T13:43:26Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Francisco Miranda Soares da Silva Neto.pdf: 1968720 bytes, checksum: 60383d7751d95b545cae9a16a83f611c (MD5) Previous issue date: 2014-02-27 / In recent years, the diminishing rate with which we can increase the amount of transistors in a processor core has slowed down the increase of computers’ power. Moore’s Law appears to be drawing to an end. With it, the assumption that software written today will be more efficiently executed in the future simply due to processors’ evolution is being challenged. On the other hand, parallel applications can still be made more efficient by distributing work among different processors to be executed at the same time, thus reducing overall execution time. To enable parallelization, we must have multiple processor cores. This has led to the popularization of multicore architectures. However, writing parallel applications is not trivial. A program must be either written from the start to be executed in parallel, or later adapted for parallel execution. The programmer has the error-prone task of parallelizing the application through use of concurrency and parallelism constructs. Locking, the most common concurrency option, presents risks for inexperienced programmers, such as the famous Deadlock and Livelock problems. As we move from single core architectures to multicore, our programming languages need to make it easier for the programmers to use concurrency. Many researchers have pointed at Software Transactional Memory (STM) as an answer to that issue, as it is a lock-free, abstract way to guarantee isolated access to shared resources. But adapting for STM a program that uses lock is not simple. Besides being an error-prone task, technical details of the language might require special attention to preserve the program’s behavior. In this dissertation, we propose a set of program transformations for concurrency constructs in Haskell, a purely functional programming language. They may be used to refactor a program’s existing locks into transactional constructs from Haskell’s STM implementation. This allows a programmer to gain the benefits of working on STM even for programs which were already developed using locks. Each transformation is accompanied by execution examples and a discussion on its ability to preserve program behavior. We also present a supporting study, in which a controlled experiment was used to evaluate the benefits of locks or STM for the development of Haskell programs. Although subjects’ opinions tended to favor lock-based concurrency, those which used STM overall committed significantly fewer mistakes and required on average 12% less time to finish their assignments. / Recentemente, a queda na taxa de crescimento da quantidade de transístores integráveis em processadores tem desacelerado o crescimento de poder computacional. A lei de Moore parece aproximar-se de seu fim. Com isso, é desafiada a premissa de que software escrito hoje terá melhor desempenho no futuro simplesmente devido à evolução dos processadores. Ainda assim, aplicações paralelas ainda podem se tornar mais eficientes ao se distribuir trabalho entre diferentes processadores para execução simultânea. Para permitir a paralelização, são necessários múltiplos núcleos de processamento, o que tem levado à popularização de arquiteturas multinúcleo. Entretanto, a escrita de aplicações paralelas não é trivial. Deve-se escrever um programa para execução paralela desde sua concepção, ou adaptá-lo posteriormente para execução paralela. O programador tem a difícil tarefa de paralelização da aplicação através do uso de construções de concorrência e paralelismo. Travas, a mais comum opção para concorrência, apresentam riscos para programadores inexperientes, tais quais os famosos problemas de Deadlock e Livelock. Ao adaptarem-se de arquiteturas de um único núcleo para as de multinúcleo, as linguagens de programação precisam facilitar o uso de concorrência para os programadores. Muitos pesquisadores têm indicado Memória Transacional em Software (STM, do inglês Software Transactional Memory) como a resposta para esse problema, por ser uma forma abstrata e não bloqueante para garantia de acesso isolado a recursos compartilhados. Mas adaptar para STM programas que usam travas não é simples. Além de ser uma atividade propensa a erros, detalhes técnicos da linguagem podem requerer cuidados para se preservar o comportamento do programa. Nesta dissertação, é proposto um conjunto de transformações de programas para construções de concorrência em Haskell, uma linguagem de programação puramente funcional. Elas podem ser usadas para refatorar travas de um programa para uso de construções transacionais da implementação de STM em Haskell. Isso permite ao programador aproveitar os benefícios do trabalho com STM mesmo para programas já desenvolvidos com uso de travas. Cada transformação é acompanhada de exemplos de execução e uma discussão sobre sua capacidade de preservar o comportamento do programa. Também é apresentado um estudo de apoio, no qual um experimento controlado foi usado para avaliar os benefícios do uso de travas ou STM no desenvolvimento de programas em Haskell. Apesar das opiniões dos participantes terem favorecido o uso de travas, aqueles que usaram STM cometeram em geral menos erros e em média precisaram de 12% a menos de tempo para terminar suas tarefas.

Orientador: Sandro Rigo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-13T10:38:16Z (GMT). No. of bitstreams: 1 Kronbauer_FernandoAndre_M.pdf: 3637569 bytes, checksum: 4c5752e2ae7f853d3b5f4971d6d7cbab (MD5) Previous issue date: 2009 / Resumo: Enquanto que arquiteturas paralelas vão se tornando cada vez mais comuns na indústria de computação mais e mais programadores precisam escrever programas paralelos e desta forma são expostos aos problemas relacionados ao uso dos mecanismos tradicionais de controle de concorrência. Memórias transacionais têm sido propostas como um meio de aliviar as dificuldades encontradas ao escreverem-se programas paralelos: o desenvolvedor precisa apenas marcar as seções de código que devem ser executadas de forma atômica e isolada - na forma de transações, e o sistema cuida dos detalhes de sincronização. Neste traba­lho exploramos propostas de memórias transacionais com suporte específico em hardware (HTM), desenvolvendo uma plataforma flexível para a prototipagem, simulação e carac­terização destes sistemas. Também exploramos um sistema de memória transacional com suporte apenas em software (STM), apresentando uma abordagem nova para gerenciar a contenção entre transações. Esta abordagem leva em consideração os padrões de acesso aos diferentes dados de um programa ao escolher o gerenciador de contenção a ser usado para o acesso a estes dados. Elaboramos uma modificação da plataforma de STM que nos permite realizar esta associação entre dados e gerenciamento de contenção, e a partir desta implementação realizamos uma caracterização baseada nos padrões de acesso aos dados de um programa executando em diferentes sistemas de computação. Os resultados de nosso trabalho mostram a viabilidade do uso de memórias transacionais em um ambi­ente de pesquisa acadêmica, e apontam caminhos para a realização de trabalhos futuros que aumentem a viabilidade do seu uso também pela indústria. / Abstract: As parallel architectures become prevalent in the computer industry, more and more programmers are required to write parallel programs and are thus being exposed to the problems related to the use of traditional mechanisms for concurrency control. Transactional memory has been devised as a means for easing the burden of writing parallel Programs: the programmer has only to mark the sections of code that are to be executed in an atomic and isolated way - in the form of transactions, and the system takes care of the synchronization details. In this work we explore different proposals of transactional memories based on specific hardware support (HTM), developing a flexible platform for the prototyping, simulation and characterization of these systems. We also explore a transactional memory system based solely on software support (STM), devising a novel approach for managing the contention among transactions. This new approach takes into account access patterns to different data in an application when choosing the contention management strategy to be used for the access to these data. We made modifications to the STM system in order to enable the association of the data with the contention manager algorithm, and using the new implementation we characterized the STM system based on the access patterns to the data of a program, running it on different hardware. Our results show the viability of the use of transactional memories in an academic environment, and serve as a basis for the proposal of different directions to be followed in future research work, aimed at leveraging the use of transactional memories by the industry. / Mestrado / Mestre em Ciência da Computação

Centralized databases are becoming bottleneck for organizations that are physically distributed and access data remotely. Data management is easy in centralized databases. However, it carries high communication cost and most importantly high response time. The concept of distributing the data over various locations is very attractive for such organizations. In such cases the database is fragmented into fragments and distributed to the locations where it is needed. This kind of distribution provides local control of data and the data access is also very fast in such databases. However, concurrency control, query optimization and data allocations are the factors that affect the response time and must be investigated prior to implementing distributed databases. This thesis makes the use of mixed method approach to meet its objective. In quantitative section, we performed an experiment to compare the response time of two databases; centralized and fragmented/distributed. The experiment was performed at Ericsson. A literature review was also done to find out other important response time related issues like query optimization, concurrency control and data allocation. The literature review revealed that these factors can further improve the response time in distributed environment. Results of the experiment showed a substantial decrease in the response time due to the fragmentation and distribution. / Centraliserade databaser blir flaskhals för organisationer som är fysiskt distribuerade och tillgång till data på distans. Datahantering är lätt i centrala databaser. Men bär den höga kostnaden kommunikation och viktigast av hög svarstid. Konceptet att distribuera data över olika orter är mycket attraktiv för sådana organisationer. I sådana fall databasen är splittrade fragment och distribueras till de platser där det behövs. Denna typ av distribution ger lokal kontroll av uppgifter och dataåtkomst är också mycket snabb i dessa databaser. Men, samtidighet kontroll, frågeoptimering och data anslagen är de faktorer som påverkar svarstiden och måste utredas innan genomförandet distribuerade databaser. Denna avhandling gör användningen av blandade metod strategi för att nå sitt mål. I kvantitativa delen utförde vi ett experiment för att jämföra svarstid på två databaser, centraliserad och fragmenterad / distribueras. Försöket utfördes på Ericsson. En litteraturstudie har gjorts för att ta reda på andra viktiga svarstid liknande frågor som frågeoptimering, samtidighet kontroll och data tilldelning. Litteraturgenomgången visade att dessa faktorer ytterligare kan förbättra svarstiden i distribuerad miljö. Resultaten av försöket visade en betydande minskning av den svarstid på grund av splittring och distribution.

Context. Name-bounded analysis is a type of static analysis that allows us to take a concurrent program, abstract away from it, and check for some interesting properties, such as deadlock-freedom, or watching the propagation of variables across different components or layers of the system. Objectives. In this study we investigate the difficulties of giving a representation of computer programs in a name-bounded variation of π-calculus. Methods. A preliminary literature review is conducted to assess the presence (or lack thereof) of other successful translations from real-world programming languages to π-calculus, as well for the presence of relevant prior art in the modelling of concurrent systems. Results. This thesis gives a novel translation going from a relevant subset of the Java programming language, to its corresponding name-bounded π-calculus equivalent. In particular, the strengths of our translation are being able to dispose of names representing inactive objects when there are no circular references, and a transparent handling of polymorphism and dynamic method resolution. The resulting processes can then be further transformed into their Petri-Net representation, enabling us to check for important properties, such as reachability and coverability of program states. Conclusions. We conclude that some important properties that are not, in general, easy to check for concurrent programs, can be in fact be feasibly determined by giving a more constrained model in π-calculus first, and as Petri Nets afterwards. / +49 151 52966429

Concurrency is generally considered to be difficult due to a lack of appropriate abstraction, rather than inherent complexity. Lock-based approaches to mutual exclusion are pervasive, despite the presence of models that are easier to understand, such as the message-passing model present in CSP (Communicating Sequential Processes). CSP provides a rich framework for building and reasoning about concurrent systems, but has historically required a change of programming language or paradigm in order to work with it. The Go programming language is a modern, imperative programming language that includes native support for processes and channels. The popularity of this language has grown and more and more people are being exposed to the fundamental ideas of CSP. There is a gap in the understanding of how a restrictive formal model can interact with and support the development of concurrent programs in a language such as Go. Through a series of case studies and analysis, we show how the CSP concurrency model can be used as the basis for the design of a concurrent system architecture without requiring the program to be written entirely as the composition of processes. It is also possible to use the CSP process algebra to build abstract models and use model-checking tools to verify properties of a concurrent system. These models can then be used to guide the decomposition of a system into a more fine-grained concurrent system. This thesis bridges the gap between the development of CSP-style concurrent software and the formal model of CSP. In particular, it shows how it is not necessary for a program or programming language to conform to rigid structure in order for CSP to be a useful tool for the development of reliable and easy to understand concurrent systems.

L’utilisation de concepts avancés de programmation concurrente permet de dépasser les inconvénients de l’utilisation de techniques de bas niveau à base de verrous ou de moniteurs. Elle augmente le niveau d’abstraction, libérant les programmeurs d’applications concurrentes d’une focalisation excessive sur des détails. Cependant, avec les approches actuelles, la logique nécessaire à la mise en place de schémas de coordinations complexes est fragmentée en plusieurs points de l’application sous forme de« join patterns », de notifications et de la logique applicative qui crée implicitement des dépendances entre les canaux de communication et donc, indirectement, les « join patterns » (qui définissent ces canaux). Nous présentons JEScala, un langage qui capture les schémas de coordination (d’une application concurrente) d’une manière plus expressive et modulaire, en s’appuyant sur l’intégration fine d’un système d’évènements avancé et des « join patterns ». Nous implémentons des automates finis à partir de « joins » à l’aide de JEScala et introduisons un langage dédié à la définition de ces automates finis permettant d’en obtenir des implémentations plus efficaces. Nous validons notre approche avec des études de cas et évaluons l’efficacité de son exécution. Nous comparons la performance de trois implémentations d’un automate fini. Nous validons enfin l’idée d’un moniteur d’évènements en créant un programme JEScala concurrent à partir d’un découpage d’un programme séquentiel. / The advanced concurrency abstractions provided by the Join calculus overcome the drawbacks of low-level techniques such as locks and monitors. They rise the level of abstraction, freeing programmers that implement concurrent applications from the burden of concentrating on low-level details. However, with current approaches the coordination logic involved incomplex coordination schemas is fragmented into several pieces including join patterns, data emissions triggered in different places of the application, and the application logic that implicitly creates dependencies among channels, hence indirectly among join patterns. We present JEScala, a language that captures coordination schemas in a more expressive and modular way by leveraging a seamless integration of an advanced event system with join abstractions. We implement Joins-based state machines using JEScala and introduce a domain specific language for finite state machines that make faster alternative implementations possible. We validate our approach with case studies and we provide a first performance assessment. We compare the performance of three different implementations of a finite state machine. Finally, we validate the idea of constructing a concurrent JEScala program by using the parts of a sequential Event-Based program in combination with an event monitor, a component that synchronizes handling of multiple events.

Le domaine des protocoles tolérants aux pannes étudie quelles tâches concurrentes sont résolubles dans différents modèles de calcul avec pannes. Des outils mathématiques basés sur la topologie combinatoire ont été développés depuis les années 1990 pour aborder ces questions. Dans ce cadre, la tâche que l’on veut résoudre, et le protocole auquel on fait appel, sont modélisés par des complexes simpliciaux chromatiques. On définit qu’un protocole résout une tâche lorsqu’il existe une certaine application simpliciale entre ces complexes.Dans cette thèse, on étudie ces méthodes géométriques du point de vue de la sémantique. Le premier objectif est de fonder cette définition abstraite de résolution d’une tâche sur une autre plus concrète, basée sur des entrelacements de traces d’exécution. On examine diverses notions de spécifications pour les objets concurrents, afin de définir un cadre général pour la résolution de tâches par des objets partagés. On montre ensuite comment extraire de ce cadre la définition topologique de résolubilité de tâches.Dans la deuxième partie de la thèse, on prouve que les complexes simpliciaux chromatiques peuvent être utilisés pour évaluer des formules de logique épistémique. Cela permet d’interpréter les preuves topologiques d’impossibilité en fonction de la quantité de connaissances à acquérir pour résoudre une tâche.Enfin, on présente quelques liens préliminaires avec la sémantique dirigée pour les programmes concurrents. On montre comment la subdivision chromatique d’un simplexe peut être retrouvée en considérant des notions combinatoires de chemins dirigés. / The field of fault-tolerant protocols studies which concurrent tasks are solvable in various computational models where processes may crash. To answer these questions, powerful mathematical tools based on combinatorial topology have been developed since the 1990’s. In this approach, the task that we want to solve, and the protocol that we use to solve it, are both modeled using chromatic simplicial complexes. By definition, a protocol solves a task when there exists a particular simplicial map between those complexes.In this thesis we study these geometric methods from the point of view of semantics. Our first goal is to ground this abstract definition of task solvability on a more concrete one, based on interleavings of execution traces. We investigate various notions of specification for concurrent objects, in order to define a general setting for solving concurrent tasks using shared objects. We then show how the topological definition of task solvability can be derived from it.In the second part of the thesis, we show that chromatic simplicial complexes can actually be used to interpret epistemic logic formulas. This allows us to understand the topological proofs of task unsolvability in terms of the amount of knowledge that the processes should acquire in order to solve a task.Finally, we present a few preliminary links with the directed space semantics for concurrent programs. We show how chromatic subdivisions of a simplex can be recovered by considering combinatorial notions of directed paths.

Multi-core processors require a program to be decomposable into independent parts that can execute in parallel in order to scale performance with the number of cores. But parallel programming is hard especially when the program requires state, which many system programs use for optimization, such as for example a cache to reduce disk I/O. Most prevalent parallel programming models do not support a notion of state and require the programmer to synchronize state access manually, i.e., outside the realms of an associated optimizing compiler. This prevents the compiler to introduce parallelism automatically and requires the programmer to optimize the program manually. In this dissertation, we propose a programming language/compiler co-design to provide a new programming model for implicit parallel programming with state and a compiler that can optimize the program for a parallel execution. We define the notion of a stateful function along with their composition and control structures. An example implementation of a highly scalable server shows that stateful functions smoothly integrate into existing programming language concepts, such as object-oriented programming and programming with structs. Our programming model is also highly practical and allows to gradually adapt existing code bases. As a case study, we implemented a new data processing core for the Hadoop Map/Reduce system to overcome existing performance bottlenecks. Our lambda-calculus-based compiler automatically extracts parallelism without changing the program's semantics. We added further domain-specific semantic-preserving transformations that reduce I/O calls for microservice programs. The runtime format of a program is a dataflow graph that can be executed in parallel, performs concurrent I/O and allows for non-blocking live updates.