Many activities are comprised of temporally dependent events that must be executed in a specific chronological order. Supportive software applications must preserve these temporal dependencies. Whenever the processing of this type of an application includes transactions submitted to a database that is shared with other such applications, the transaction concurrency control mechanisms within the database must also preserve the temporal dependencies. A basis for preserving temporal dependencies is established by using (within the applications and databases) real-time timestamps to identify and order events and transactions. The use of optimistic approaches to transaction concurrency control can be undesirable in such situations, as they allow incorrect results for database read operations. Although the incorrectness is detected prior to transaction committal and the corresponding transaction(s) restarted, the impact on the application or entity that submitted the transaction can be too costly. Three transaction concurrency control algorithms are proposed in this dissertation. These algorithms are based on timestamp ordering, and are designed to preserve temporal dependencies existing among data-dependent transactions. The algorithms produce execution schedules that are equivalent to temporally ordered serial schedules, where the temporal order is established by the transactions' start times. The algorithms provide this equivalence while supporting currency to the extent out-of-order commits and reads. With respect to the stated concern with optimistic approaches, two of the proposed algorithms are risk-free and return to read operations only committed data-item values. Risk with the third algorithm is greatly reduced by its conservative bias. All three algorithms avoid deadlock while providing risk-free or reduced-risk operation. The performance of the algorithms is determined analytically and with experimentation. Experiments are performed using functional database management system models that implement the proposed algorithms and the well-known Conservative Multiversion Timestamp Ordering algorithm.

Because of the high cost and impracticality of a high connectivity network, most recent research in transaction processing has focused on a distributed replicated database system. In such a system, multiple copies of a data item are created and stored at several sites in the network, so that the system is able to tolerate more crash and communication failures and attain higher data availability. However, the multiple copies also introduce a global inconsistency problem, especially in a partitioned network. In this dissertation a tree quorum algorithm is proposed to solve this problem, imposing a logical tree structure along with dynamic system reconfiguration on all the copies of each data item. The proposed algorithm can be viewed as a dynamic voting technique which, with the help of an appropriate concurrency control algorithm, exhibits the major advantages of quorum-based replica control algorithms and of the available copies algorithm, so that a single copy is read for a read operation and a quorum of copies is written for a write operation. In addition, read and write quorums are computed dynamically and independently. As a result expensive read operations, like those that require several copies of a data item to be read in most quorum schemes, are eliminated. Furthermore, the message costs of read and write operations are reduced by the use of smaller quorum sizes. Quorum sizes can be reduced to a constant in a lightly loaded system, and log n in a failure-free network, as well as [n +1/2] in a partitioned network in a heavily loaded system. On average, our algorithm requires fewer messages than the best known tree quorum algorithm, while still maintaining the same upper bound on quorum size. One-copy serializability is guaranteed with higher data availability and highest degree of fault tolerance (up to n - 1 site failures).

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques. / Comparative genomics is essentially a form of data mining in large collections of n-ary relations between genomic elements. Increases in the number of sequenced genomes create a stress on comparative genomics that grows, at worse geometrically, for every increase in sequence data. Even modestly-sized labs now routinely obtain several genomes at a time, and like large consortiums expect to be able to perform all-against-all analyses as part of these new multi-genome strategies. In order to address the needs at all levels it is necessary to rethink the algorithmic frameworks and data storage technologies used for comparative genomics.To meet these challenges of scale, in this thesis we develop novel methods based on NoSQL and MapReduce technologies. Using a characterization of the kinds of data used in comparative genomics, and a study of usage patterns for their analysis, we define a practical formalism for genomic Big Data, implement it using the Cassandra NoSQL platform, and evaluate its performance. Furthermore, using two quite different global analyses in comparative genomics, we define two strategies for adapting these applications to the MapReduce paradigm and derive new algorithms. For the first, identifying gene fusion and fission events in phylogenies, we reformulate the problem as a bounded parallel traversal that avoids high-latency graph-based algorithms. For the second, consensus clustering to identify protein families, we define an iterative sampling procedure that quickly converges to the desired global result. For both of these new algorithms, we implement each in the Hadoop MapReduce platform, and evaluate their performance. The performance is competitive and scales much better than existing solutions, but requires particular (and future) effort in devising specific algorithms.

O presente trabalho propõe uma arquitetura de utilização de Data Warehouses em computadores móveis, descreve os componentes desta arquitetura (dados e processos) que permite o sincronismo dos dados baseado em metadados e limitado ao escopo de acesso de cada usuário. As estruturas de dados e os processos que compõem a arquitetura proposta são reduzidos a problemas conhecidos e já solucionados, justificando sua viabilidade. Além disso, o presente trabalho também fornece diretrizes para avaliar a complexidade e o impacto causados por alterações de esquema no Data Warehouse central que devem ser refletidas nos data marts localizados nas plataformas móveis. A avaliação da complexidade e impacto das alterações nos esquemas do Data Warehouse pode auxiliar os administradores do ambiente a planejar a implementação destas alterações, propondo melhores alternativas no caso de alterações de esquema mais complexas e que causem um impacto maior no ambiente. A importância do trabalho está relacionada a casos reais de necessidade de evolução nas bases de dados analíticas (Data Warehouse) em computadores móveis, nos quais os usuários mantêm seu próprio subconjunto de dados do Data Warehouse para apoiar os processos de negócios. / This work presents an architecture for using Data Warehouses in mobile computers and describes the architecture components (data and processes) that allow the data synchronism based on metadata and restricted to the scope of access for each user. The data structures and the processes composing the architecture are reduced to already known and solved problems, justifying its feasibility. Besides, this work also provides the guidelines to evaluate the complexity and impact caused by changes of schema in the central Data Warehouse that must be reflected in the data marts located in the mobile platforms. The analysis of the complexity and impact of the changes made to the schemas may help environment administrators to plan these changes and propose better alternatives when dealing with more complex schema changes causing a greater impact on the environment. The relevance of this work is related to real cases that require evolution of analytical databases (Data Warehouse) in mobile computers in which the users keep their own subset of Data Warehouse information to support their business processes.

O presente trabalho propõe uma arquitetura de utilização de Data Warehouses em computadores móveis, descreve os componentes desta arquitetura (dados e processos) que permite o sincronismo dos dados baseado em metadados e limitado ao escopo de acesso de cada usuário. As estruturas de dados e os processos que compõem a arquitetura proposta são reduzidos a problemas conhecidos e já solucionados, justificando sua viabilidade. Além disso, o presente trabalho também fornece diretrizes para avaliar a complexidade e o impacto causados por alterações de esquema no Data Warehouse central que devem ser refletidas nos data marts localizados nas plataformas móveis. A avaliação da complexidade e impacto das alterações nos esquemas do Data Warehouse pode auxiliar os administradores do ambiente a planejar a implementação destas alterações, propondo melhores alternativas no caso de alterações de esquema mais complexas e que causem um impacto maior no ambiente. A importância do trabalho está relacionada a casos reais de necessidade de evolução nas bases de dados analíticas (Data Warehouse) em computadores móveis, nos quais os usuários mantêm seu próprio subconjunto de dados do Data Warehouse para apoiar os processos de negócios. / This work presents an architecture for using Data Warehouses in mobile computers and describes the architecture components (data and processes) that allow the data synchronism based on metadata and restricted to the scope of access for each user. The data structures and the processes composing the architecture are reduced to already known and solved problems, justifying its feasibility. Besides, this work also provides the guidelines to evaluate the complexity and impact caused by changes of schema in the central Data Warehouse that must be reflected in the data marts located in the mobile platforms. The analysis of the complexity and impact of the changes made to the schemas may help environment administrators to plan these changes and propose better alternatives when dealing with more complex schema changes causing a greater impact on the environment. The relevance of this work is related to real cases that require evolution of analytical databases (Data Warehouse) in mobile computers in which the users keep their own subset of Data Warehouse information to support their business processes.

Grades computacionais tem a finalidade de oferecer meios para o compartilhamento de recursos distribuídos geograficamente para o uso em aplicações que necessitem. A integração de Bancos de Dados distribuídos geograficamente pode ser obtida através do compartilhamento de recursos provido pela tecnologia de grades. Este trabalho utiliza middlewares de grade computacional, especificamente Globus e OGSA-DAI bem como outras tecnologias como LDAP e JDBC, especificando uma arquitetura distribuída para possibilitar a integração de Bancos de Dados, oferecendo também suporte a replicação. A arquitetura proposta possibilita a configuração de níveis hierárquicos de replicação. O presente trabalho apresenta a implementação de um protótipo desta arquitetura. Um driver JDBC é apresentado para possibilitar o uso dos bancos de dados expostos na grade. Tem-se como resultado deste trabalho, a definição da arquitetura e o desenvolvimento de ferramentas culminando em um protótipo funcional, bem como uma versão estável do driver JDBC. A possibilidade de integração de bancos de dados na grade com suporte a replicação, torna possível aplicações de alto desempenho e alta disponibilidade sem comprometer a autonomia local dos bancos de dados integrados. / Grid Computing have the goal of providing means to share resources to be used by applications that need these resources. The integration of geographically distributed databases can be obtained by sharing resources using grid computing technology. This work uses grid middlewares, specifically Globus Toolkit and OGSA-DAI, as well as other technologies as LDAP and Java JDBC, specifying a distributed architecture to allow database integration, also offering support for replication. The proposed architecture offers also its configuration in hierarchical levels of replication. The work also presents the implementation of a prototype based on the proposed architecture. A JDBC driver is presented, it allows the ease access to databases exposed in the grid. The results of this work are the definition of the architecture, the development of a functional prototype and a stable version of the JDBC Driver. The possibility of integrating databases with replication support allows applications of high performance and high availability without interfering in the local autonomy of the databases.

Grades computacionais tem a finalidade de oferecer meios para o compartilhamento de recursos distribuídos geograficamente para o uso em aplicações que necessitem. A integração de Bancos de Dados distribuídos geograficamente pode ser obtida através do compartilhamento de recursos provido pela tecnologia de grades. Este trabalho utiliza middlewares de grade computacional, especificamente Globus e OGSA-DAI bem como outras tecnologias como LDAP e JDBC, especificando uma arquitetura distribuída para possibilitar a integração de Bancos de Dados, oferecendo também suporte a replicação. A arquitetura proposta possibilita a configuração de níveis hierárquicos de replicação. O presente trabalho apresenta a implementação de um protótipo desta arquitetura. Um driver JDBC é apresentado para possibilitar o uso dos bancos de dados expostos na grade. Tem-se como resultado deste trabalho, a definição da arquitetura e o desenvolvimento de ferramentas culminando em um protótipo funcional, bem como uma versão estável do driver JDBC. A possibilidade de integração de bancos de dados na grade com suporte a replicação, torna possível aplicações de alto desempenho e alta disponibilidade sem comprometer a autonomia local dos bancos de dados integrados. / Grid Computing have the goal of providing means to share resources to be used by applications that need these resources. The integration of geographically distributed databases can be obtained by sharing resources using grid computing technology. This work uses grid middlewares, specifically Globus Toolkit and OGSA-DAI, as well as other technologies as LDAP and Java JDBC, specifying a distributed architecture to allow database integration, also offering support for replication. The proposed architecture offers also its configuration in hierarchical levels of replication. The work also presents the implementation of a prototype based on the proposed architecture. A JDBC driver is presented, it allows the ease access to databases exposed in the grid. The results of this work are the definition of the architecture, the development of a functional prototype and a stable version of the JDBC Driver. The possibility of integrating databases with replication support allows applications of high performance and high availability without interfering in the local autonomy of the databases.

[No Abstract]

State monitoring is a fundamental building block for Cloud services. The demand for providing state monitoring as services (MaaS) continues to grow and is evidenced by CloudWatch from Amazon EC2, which allows cloud consumers to pay for monitoring a selection of performance metrics with coarse-grained periodical sampling of runtime states. One of the key challenges for wide deployment of MaaS is to provide better balance among a set of critical quality and performance parameters, such as accuracy, cost, scalability and customizability. This dissertation research is dedicated to innovative research and development of an elastic framework for providing state monitoring as a service (MaaS). We analyze limitations of existing techniques, systematically identify the need and the challenges at different layers of a Cloud monitoring service platform, and develop a suite of distributed monitoring techniques to support for flexible monitoring infrastructure, cost-effective state monitoring and monitoring-enhanced Cloud management. At the monitoring infrastructure layer, we develop techniques to support multi-tenancy of monitoring services by exploring cost sharing between monitoring tasks and safeguarding monitoring resource usage. To provide elasticity in monitoring, we propose techniques to allow the monitoring infrastructure to self-scale with monitoring demand. At the cost-effective state monitoring layer, we devise several new state monitoring functionalities to meet unique functional requirements in Cloud monitoring. Violation likelihood state monitoring explores the benefits of consolidating monitoring workloads by allowing utility-driven monitoring intensity tuning on individual monitoring tasks and identifying correlations between monitoring tasks. Window based state monitoring leverages distributed windows for the best monitoring accuracy and communication efficiency. Reliable state monitoring is robust to both transient and long-lasting communication issues caused by component failures or cross-VM performance interferences. At the monitoring-enhanced Cloud management layer, we devise a novel technique to learn about the performance characteristics of both Cloud infrastructure and Cloud applications from cumulative performance monitoring data to increase the cloud deployment efficiency.

<p>Distributed real-time databases can be used to support data sharing</p><p>for applications in wireless ad-hoc networks. In such networks, topology changes frequently and partitions may be unpredictable and last for an unbounded period. In this thesis, the existing database replication protocol PRiDe is extended to handle such long-lasting partitions. The protocol uses optimistic and detached replication to provide predictable response times in unpredictable networks and forward conflict resolution to guarantee progress.</p><p>The extension, pPRiDe, combines update and state transfer strategies. Update transfer for intra-partition communication can reduce bandwidth usage and ease conflict resolution. State transfer for inter partition conflicts removes dependency on a common state between partitions prior to the merge to apply update messages on. This makes the resource usage independent of the life span of partitions. This independence comes at the cost of global data stability guarantees and pPRiDe can thus only provide per partition guarantees. The protocol supports application specific conflict resolution routines for both</p><p>state and update conflicts. A basic simulator for mobile ad-hoc networks has been developed to validate that pPRiDe provides eventual consistency.</p><p>pPRiDe shows that a hybrid approach to change propagation strategy can be beneficial in networks where collaboration by data sharing within long lasting partitions and predictable resource usage is necessary. These types of systems already require the conflict management routines necessary for pPRiDe and can benefit from an existing protocol.</p><p>In addition to pPRiDe and the simulator this thesis provides a flexible object database suitable for future works and an implementation of PRiDe on top of that database.</p>