<div> <div> <div> <p>The performance bottlenecks in modern data-intensive applications have induced database implementors to forsake high-level abstractions and trade-off simplicity and ease of reasoning for performance. Among the first casualties of this trade-off are the well-known ACID guarantees, which simplify the reasoning about concurrent database transactions. ACID semantics have become increasingly obsolete in practice due to serializable isolation – an integral aspect of ACID, being exorbitantly expensive. Databases, including the popular commercial offerings, default to weaker levels of isolation where effects of concurrent transactions are visible to each other. Such weak isolation guarantees, however, are extremely hard to reason about, and have led to serious safety violations in real applications. The problem is further complicated in a distributed setting with asynchronous state replications, where high availability and low latency requirements compel large-scale web applications to embrace weaker forms of consistency (e.g., eventual consistency) besides weak isolation. Given the serious practical implications of safety violations in data-intensive applications, there is a pressing need to extend the state-of-the-art in program verification to reach non- serializable data-intensive applications operating in a weakly-consistent distributed setting. </p> <p>This thesis sets out to do just that. It introduces new language abstractions, program logics, reasoning methods, and automated verification and synthesis techniques that collectively allow programmers to reason about non-serializable data-intensive applications in the same way as their serializable counterparts. The contributions </p> </div> </div> <div> <div> <p>xi </p> </div> </div> </div> <div> <div> <div> <p>made are broadly threefold. Firstly, the thesis introduces a uniform formal model to reason about weakly isolated (non-serializable) transactions on a sequentially consistent (SC) relational database machine. A reasoning method that relates the semantics of weak isolation to the semantics of the database program is presented, and an automation technique, implemented in a tool called ACIDifier is also described. The second contribution of this thesis is a relaxation of the machine model from sequential consistency to a specifiable level of weak consistency, and a generalization of the data model from relational to schema-less or key-value. A specification language to express weak consistency semantics at the machine level is described, and a bounded verification technique, implemented in a tool called Q9 is presented that bridges the gap between consistency specifications and program semantics, thus allowing high-level safety properties to be verified under arbitrary consistency levels. The final contribution of the thesis is a programming model inspired by version control systems that guarantees correct-by-construction <i>replicated data types</i> (RDTs) for building complex distributed applications with arbitrarily-structured replicated state. A technique based on decomposing inductively-defined data types into <i>characteristic relations</i> is presented, which is used to reason about the semantics of the data type under state replication, and eventually derive its correct-by-construction replicated variant automatically. An implementation of the programming model, called Quark, on top of a content-addressable storage is described, and the practicality of the programming model is demonstrated with help of various case studies. </p> </div> </div> </div>

Multidatabases are being actively researched as a relatively new area in which many aspects are not yet fully understood. This area of transaction management in multidatabase systems still has many unresolved problems. The problem areas which this dissertation addresses are classification of multidatabase systems, global concurrency control, correctness criterion in a multidatabase environment, global deadlock detection, atomic commitment and crash recovery. A core group of research addressing these problems was identified and studied. The dissertation contributes to the multidatabase transaction management topic by introducing an alternative classification method for such multiple database systems; assessing existing research into transaction management schemes and based on this assessment, proposes a transaction processing model founded on the optimal properties of transaction management identified during the course of this research. / Computing / M. Sc. (Computer Science)

Orientador: Maria Beatriz Felgar de Toledo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T08:41:15Z (GMT). No. of bitstreams: 1 Pierre_AllynGreydeAlmeidaLima_M.pdf: 1760009 bytes, checksum: 4af51767131cfa3c30ee8f7ea8830949 (MD5) Previous issue date: 2009 / Resumo: Dentre as tecnologias emergentes, a computação móvel tem a sua posição de destaque. Os dispositivos móveis estão mais presentes na vida das pessoas e contendo aplicações mais sofisticadas e semelhantes às executadas em computadores pessoais. Num mundo globalizado, onde o tempo é escasso e valioso, os dispositivos móveis mantêm as pessoas em contato com informações e atividades que elas desejam enquanto elas estão em movimento. Um exemplo recente é aumento do uso da internet em celulares, permitindo que os usuários acessem diversos tipos de aplicações, tendo grande parte delas interação com bancos de dados. Apesar de atrativa, a computação móvel traz desafios ao desenvolvedor, pois ele deve considerar os recursos limitados tais como largura de banda, conectividade e o alto custo da obtenção de dados. Nesse contexto, as transações representam um importante papel de garantir que o dinamismo do ambiente da computação móvel não comprometa a confiabilidade das aplicações. Porém, algumas aplicações não podem ser implementadas considerando o modelo de transações tradicional, pois elas têm um tempo mais longo de duração do que aquelas convencionalmente modeladas. Sendo assim, as configurações de uma transação realizadas no início de sua execução podem deixar de ser adequadas no decorrer da sua execução, devido às mudanças no ambiente. Diversos modelos de transações têm sido apresentados na literatura para atender a esse ambiente. Apesar de muitas idéias interessantes e relevantes, alguns modelos não permitem que a adaptação diante da variação dos recursos seja realizada durante a execução de uma transação e quando permitem, eles realizam grandes reconfigurações arquiteturais. Motivada por essas questões, essa dissertação propõe transações reconfiguráveis, isto é, a configuração dinâmica de mecanismos transacionais antes do início da transação e a reconfiguração de propriedades transacionais durante sua execução. Para que a reconfiguração dinâmica fosse realizada, um modelo de componentes chamado OpenCOM foi utilizado na arquitetura proposta, por este ser reflexivo, leve e independente de plataforma. O nível de isolamento é a propriedade transacional que poderá ser reconfigurada durante a transação e o controle de concorrência é o mecanismo que garantirá o isolamento entre as transações e poderá ser configurado antes do início da transação. A configuração do controle de concorrência é uma contribuição inovadora dessa dissertação, pois em muitos trabalhos existentes não é possível a configuração desse mecanismo transacional. A fim de validar a arquitetura proposta, um protótipo de um sistema de vendas foi desenvolvido. Através dessa implementação foi possível analisar os impactos da reconfiguração durante uma transação / Abstract: Among the emerging technologies, mobile computing has its position of prominence. Mobile devices are more present in people's lives and with more sophisticated applications similar to those implemented in personal computers. In a globalized world where time is scarce and of great importance, mobile devices keep people in touch with information and activities they want while they are moving. A recent example is the increasing use of the Internet on mobile phones allowing users to access various types of applications and much of them interacting with databases. Although attractive, the mobile computing brings challenges to the developer because he must consider the limited resources such as bandwidth, connectivity and the high cost of obtaining data. In this context, the transactions represent an important role to ensure that the dynamic environment of mobile computing does not compromise the reliability of applications. However some applications cannot be implemented given the traditional transactions models because they have a longer duration than those conventionally shaped. Therefore the settings of a transaction carried out before its execution may not be appropriate during the execution due to changes in the environment. Various transactions models have been reported in the literature to serve this environment. Although having many interesting and relevant ideas, some models do not allow the adaptation in the face of change of resources during the execution of a transaction and when this is allowed, they require many transactional reconfigurations. Motivated by these issues, this dissertation proposes reconfigurable transactions that are the dynamic configuration of transactional mechanisms before the beginning of the transaction and the reconfiguration of transactional properties during its execution. For dynamic reconfiguration, a component model called OpenCOM has been used in the proposed architecture because it is reflective, lightweight and platform-independent. The isolation level is the property that may be reconfigured during the transaction and the concurrency control is the mechanism that ensures the isolation between the transactions and it can be configured before the beginning of transaction. The configuration of concurrency control is an original contribution of this dissertation because many works do not allow the configuration of this transactional mechanism. In order to validate the proposed architecture, a prototype of a sales system has been developed. Through this implementation it was possible to analyze the impacts of the reconfiguration during a transaction / Mestrado / Sistemas Distribuidos / Mestre em Ciência da Computação

With the shifting landscape of computing hardware architectures and the emergence of new computing environments (e.g., large main-memory systems, hundreds of CPUs, distributed and virtualized cloud-based resources), state-of-the-art designs of transaction processing systems that rely on conventional wisdom suffer from lost performance optimization opportunities. This dissertation challenges conventional wisdom to rethink the design and implementation of transaction processing systems for modern computing environments.<div><br></div><div>We start by tackling the vertical hardware scaling challenge, and propose a deterministic approach to transaction processing on emerging multi-sockets, many-core, shared memory architecture to harness its unprecedented available parallelism. Our proposed priority-based queue-oriented transaction processing architecture eliminates the transaction contention footprint and uses speculative execution to improve the throughput of centralized deterministic transaction processing systems. We build QueCC and demonstrate up to two orders of magnitude better performance over the state-of-the-art.<br></div><div><br></div><div>We further tackle the horizontal scaling challenge and propose a distributed queue-oriented transaction processing engine that relies on queue-oriented communication to eliminate the traditional overhead of commitment protocols for multi-partition transactions. We build Q-Store, and demonstrate up to 22x improvement in system throughput over the state-of-the-art deterministic transaction processing systems.<br></div><div><br></div><div>Finally, we propose a generalized framework for designing distributed and replicated deterministic transaction processing systems. We introduce the concept of speculative replication to hide the latency overhead of replication. We prototype the speculative replication protocol in QR-Store and perform an extensive experimental evaluation using standard benchmarks. We show that QR-Store can achieve a throughput of 1.9 million replicated transactions per second in under 200 milliseconds and a replication overhead of 8%-25%compared to non-replicated configurations.<br></div>