The Lenstra, Lenstra and Lov\'sz (LLL) reduction is the most popular lattice reduction and is a powerful tool for solving many complex problems in mathematics and computer science. The blocking technique casts matrix algorithms in terms of matrix-matrix operations to permit efficient reuse of data in the algorithms. In this thesis, we use the blocking technique to develop two floating point block LLL reduction algorithms, the left-to-right block LLL (LRBLLL) reduction algorithm and the alternating partition block LLL (APBLLL) reduction algorithm, and give the complexity analysis of these two algorithms. We compare these two block LLL reduction algorithms with the original LLL reduction algorithm (in floating point arithmetic) and the partial LLL (PLLL) reduction algorithm in the literature in terms of CPU run time, flops and relative backward errors. The simulation results show that the overall CPU run time of the two block LLL reduction algorithms are faster than the partial LLL reduction algorithm and much faster than the original LLL, even though the two block algorithms cost more flops than the partial LLL reduction algorithm in some cases. The shortcoming of the two block algorithms is that sometimes they may not be as numerically stable as the original and partial LLL reduction algorithms. The parallelization of APBLLL is discussed. / Le Lenstra, Lenstra et réduction Lovasz (LLL) est la réduction de réseaux plus populaire et il est un outil puissant pour résoudre de nombreux problèmes complexes en mathématiques et en informatique. La technique bloc LLL bloquante reformule les algorithmes en termes de matrice-matrice opérations de permettre la réutilisation efficace des données dans les algorithmes bloc LLL. Dans cette thèse, nous utilisons la technique de blocage de développer les deux algorithmes de réduction bloc LLL en points flottants, l'algorithme de réduction bloc LLL de la gauche vers la droite (LRBLLL) et l'algorithme de réduction bloc LLL en partition alternative (APBLLL), et donner a l'analyse de la complexité des ces deux algorithmes. Nous comparons ces deux algorithmes de réduction bloc LLL avec l'algorithme de réduction LLL original (en arithmétique au point flottant) et l'algorithme de réduction LLL partielle (PLLL) dans la littérature en termes de temps d'exécution CPU, flops et les erreurs de l'arrière par rapport. Les résultats des simulations montrent que les temps d'exécution CPU pour les deux algorithmes de réduction blocs LLL sont plus rapides que l'algorithme de réduction LLL partielle et beaucoup plus rapide que la réduction LLL originale, même si les deux algorithmes par bloc coûtent plus de flops que l'algorithme de réduction LLL partielle dans certains cas. L'inconvénient de ces deux algorithmes par blocs, c'est que parfois, ils peuvent n'être pas aussi stable numériquement que les algorithmes originaux et les algorithmes de réduction LLL partielle. Le parallélisation de APBLLL est discutée.

Radio Frequency Identification (RFID) technology is widely used for variousapplications from access control to object tracking systems. Automation and fasterservices provided by this technology have striking effects on our daily life. However,there are several security and privacy concerns about RFID systems that remainunsolved. During the past years, several attacks have been designed against MifareClassic and HID iClass, two of the most widely used RFID systems on the market.The aim of this study was to improve the security and privacy mechanisms of RFIDsystems through the development of tools and the methodology of system analysis, inthe hope to find the possible flaws before the adversaries do. As an example, effortswere made to partially analyze OPUS cards (the RFID-enabled public transportationpasses in Montreal) and several security and privacy violating specifications of thesecards were highlighted. It was revealed that the static identification number of thecard is transfered in the anticollision process which can be used to track the cardholder without his consent. In addition, the information about the last three usages ofthe card (the time, the date and the metro/bus station) are transferred unencryptedand before the authentication process. Only a linear conversion is applied to theinformation which can be reversed by a simple application such as the one developedand provided in this study.Furthermore, design modifications to improve the security and privacy level of RFIDsystems were provided. These modifications are categorized based on the cost andthe disruption of service that the application of these modifications imposes to themanufacturing company.Key Words: RFID Systems, Privacy, Security, OPUS Cards / Les technologies de radio identification (RFID) sont fortement utilisées dans diverses applications qui vont du contrôle d'accès aux systèmes de traçabilité d'objets. L'automatisation et la rapidité accrue des services que ces technologies rendent possibles ont des effets marqués sur notre vie quotidienne. Cependant, les systèmes RFID comportent de nombreux problèmes de sécurité et de protection de la vie privée qui ne sont toujours pas résolus. Au cours des dernières années, de nombreuses attaques ont été conues contre la puce Classic de MIFARE ainsi que la puce iClass d'HID, deux des systèmes RFID les plus répandus sur le marché. Le but de cette étude est d'améliorer les mécanismes de sécurité et de protection de la vie privée des systèmes RFID par le développement d'outils et la méthodologie d'analyse des systèmes, dans l'espoir de découvrir les failles de sécurité potentielles avant que des adversaires ne le fassent. Par exemple, nous avons procédé à une analyse partielle des cartes OPUS (les cartes qui contiennent les titres de transport en commun utilisés à Montréal, qui font usage de la technologie RFID), et mis en évidence de nombreux éléments des spécifications de ces cartes qui représentent une faille de sécurité ou de protection de la vie privée. Nous avons découvert que le numéro d'identification statique de la carte est transmis durant le processus anticollision, ce qui peut être utilisé pour suivre la trace du détenteur de la carte sans son consentement. De plus, des informations concernant les trois dernières utilisations d'une carte (l'heure, la date, et la station de métro ou d'autobus) sont transmis sans être chiffrés, et avant le processus d'authentification n'ait lieu. Seule une conversion linéaire est appliquée sur l'information, et cette conversion peut être inversée par une simple application telle que celle que nous avons développé au cours de cette étude. De plus, nous présentons des modifications visant à améliorer le niveau de sécurité et de protection de la vie privée des systèmes RFID. Nous classons ces modifications sur la base de leur coût et de la gravité des interruptions de service que l'application de ces modifications ferait subir au manufacturier.Mots clés: Systèmes RFID, protection de la vie privée, sécurité, cartes OPUS

Recent years have seen a huge growth in the demand for online virtual worlds. The type of these online systems can range from virtual meeting setups, to a more video game like competitive environment. An equally large number of virtual worlds have been developed to meet this demand, and the competition between these system is very strong. Developers of such systems can benefit from any edge they can get in terms of technical quality of the system or the enjoy ability of the online experience.We propose that a monitoring system designed especially for virtual worlds will be able to provide that `èdge" to the developers. As such, we present, in this Thesis, a flexible real-time monitoring architecture which caters to the specific challenges and requirements of virtual worlds. Handling huge amount of data present in the worlds is dealt by distributing the data gathering process between multiple node. The proposed system modifies the gathered data, into a form more suitable for users to observe in real-time, by filtering it before displaying the final result. We use Mammoth, a massively multiplayer research framework, as the test-bed for a sample implementation of the proposed architecture. We use the results of experiments conducted on this implementation to validate that the system is indeed suitable for real-time monitoring of virtual worlds. / De nos jours, la demande des mondes virtuels est en plein essor. Ceux-ci vont des sites de rencontre jusqu'aux environnements compétitifs comme par exemple les jeux vidéo en ligne. Afin de satisfaire la demande de mondes virtuels, de nombreux sites ont été mis en place. Du fait de la très grande concurrence présente, les développeurs des services virtuels essayent de bénéficier de tout avantage possible en termes d'avantages techniques ou de la qualité des expériences vécues en ligne.Nous considérons qu'un système de surveillance des mondes virtuels est en mesure de fournir cet "avantage" aux développeurs. Ainsi, nous présentons dans notre thèse un système de surveillance en temps réel fait sur mesure afin de faire face aux défis et aux besoins particuliers de chaque monde virtuel. Afin de manipuler toute l'information obtenue des mondes virtuels, le processus d'obtention des données est distribué entre plusieurs nœuds. Le système que nous proposons modifie les données obtenues pour les rendre plus faciles à observer en temps réel. Ceci se fait en filtrant les données avant de déployer les résultats. Nous utilisons Mammoth, une infrastructure massif de recherche multi-joueurs comme le banc d'essai pour implémenter un échantillon de l'architecture proposée. Nous utilisons les résultats obtenus des expériences réalisées dans cette implémentation pour confirmer que le système est approprié pour surveiller les mondes virtuels en temps réel.

Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1,x2,...,xn and a list of constraints of the form "(x7,x2,...,x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. In recent years, combined logical and algebraic approaches to understand the complexity of CSPs within the complexity class P have been especially fruitful. In particular, precise algebraic conditions on Γ have been conjectured to be sufficient and necessary for the membership of CSP(Γ) in the complexity classes L and NL (under standard complexity theoretic assumptions, e.g. L different from NL). These algebraic conditions are known to be necessary, and from the algorithmic side, a promising body of evidence is fast-growing. The main tools to establish membership of CSPs in L and NL are the logic programming fragments symmetric and linear Datalog, respectively. This thesis is centered around the above algebraic conjecture for CSPs in L, and most of the technical work is devoted to establishing the membership of several large classes of CSPs in L. Among other results, we characterize all graphs for which the list homomorphism problem is in L, a well-studied and natural class of CSPs. We also extend this result to obtain a complete characterization of the complexity of the list homomorphism for graphs. We develop new tool (dualities for symmetric Datalog) to show membership of CSPs in L, prove an L − NL dichotomy for the list homomorphism problem for oriented paths, provide results about the structure and polymorphisms of Maltsev digraphs, and also contribute to the conjecture of Dalmau that every CSP in NL is in fact in linear Datalog. / Les problèmes de satisfaction de contraintes (ou CSP) forment un cadre particulièrement riche permettant de formaliser de façon uniforme un grand nombre de problèmes algorithmiques tirés de l'optimisation combinatoire, de l'intelligence artificielle et de la théorie des bases de données. À chaque domaine D et chaque langage de contraintes Γ (i.e. un ensemble de relations sur D), on associe le problème CSP(Γ) suivant. Une instance du problème est constituée d'une liste de variables x1,...,xn et d'une liste de contraintes de la forme (x7,x2,...,x5) ∈ R, où R ∈ Γ. On cherche à déterminer si des valeurs de D peuvent être assignées aux variables de telle sorte que les contraintes soient toutes satisfaites simultanément. La complexité algorithmique de CSP(Γ) est entièrement fonction de la structure du langage de contraintes Γ et on cherche alors à identifier des classes de contraintes pour lesquelles CSP(Γ) appartient à une classe de complexité spécifique. Récemment, la combinaison des approches logique et algébrique a porté fruits dans la compréhension de la complexité des CSP à l'intérieur de la classe P. En particulier, on a conjecturé des conditions algébriques nécessaires et suffisantes précises pour l'appartenance de CSP(Γ) dans les classes L et NL (sous les hypothèses habituelles en théorie de la complexité, e.g. L est différent de NL). Ces conditions algébriques sont sues être nécessaires, et d'un point de vue algorithmique, les indications en faveur du résultat s'accumulent rapidement. Les outils principaux pour établir l'appartenance d'un CSP à L ou NL sont respectivement les fragments "symmetric Datalog" et "linear Datalog" en programmation logique. Notre thèse est centrée sur la conjecture algébrique ci-haut mentionnée pour les CSP dans L, et la majeure partie du travail technique est dédiée à montrer l'appartenance de plusieurs grandes familles de CSP dans L. Entre autres résultats, nous caractérisons tous les graphes pour lesquels le problème de "list homomorphism" est dans L, une famille naturelle et bien étudiée de CSP. Nous étendons aussi ce résultat pour obtenir une caractérisation complète de la question pour les graphes. Nous développons de nouveaux outils (les dualités pour "symmetric Datalog") pour montrer l'appartenance de CSP dans L, nous prouvons une dichotomie L-NL pour les problèmes de "list homomorphism" pour les chemins orientés, nous donnons des résultats sur la structure et les polymorphismes des digraphes de Maltsev, et nous contribuons à la conjecture de Dalmau à l'effet que chaque CSP dans NL est en fait dans "linear Datalog".

The majority of touch-enabled musical production software tend to use metaphors from professional musical studio environments in their interface (e.g., a rackmount, turntables plus a crossfader, or a keyboard) or simply use single-finger input as a computer mouse. We identify a need for musical software that benefits from novel graphical user interface elements and innovative metaphors to provide control over pre-recorded music. We hypothesize that a software design approach using conceptual integration, or blending, will lead to new ludic interfaces for musical expression with the potential to facilitate DJ tasks. Multi-touch technology offers the promise of going beyond traditional mouse-based user interfaces, and is especially pertinent in that it provides full embodiment: the user interacts directly with the visual feedback of the system. This change in paradigm has implications in software design, not yet fully understood in tools for musical expression.This thesis first documents the existing methods of implementing multi-touch technology, before suggesting a taxonomy of multi-touch devices. A literature review of multi-touch systems for musical applications is also presented, after which metaphor and blending (also known as conceptual integration) are discussed. We apply blending to software design for multi-touch musical software and introduce our programming framework, TactoSonix. / Dans leur interface utilisateur, la plupart des logiciels de production musicale pour écrans tactiles multipoints emploient des métaphores issues des studios de musique professionnels dans leur interface utilisateur (châssis à effets de guitare, tourne-disques, potentiomètres rectilignes, clavier), ou utilisent un doigt qui joue le rôle de souris. Cela nous a amenés à constater que ces logiciels gagneraient à inclure des éléments innovateurs au niveau de l'interface utilisateur et à employer des métaphores inexplorées dans un contexte de contrôle de morceaux de musique pré-enregistrée. Nous partons de l'hypothèse que la conception de logiciel assistée par l'intégration conceptuelle (blending) permettra le développement d'interfaces ludiques pour l'expression musicale et facilitera certaines tâches des DJs. La technologie tactile multipoints nous permet d'imaginer des interfaces de logiciels non-traditionnelles, car elle combiner les interfaces de rétroaction visuelle et de contrôle du systême. Ce changement de paradigme nous oblige à réévaluer la conception des logiciels de production musicale, et à étudier ses applications dans le domaine de l'expression musicale. Ce mémoire répertorie les méthodes qui permettent actuellement de concevoir des dispositifs tactiles multipoints dont il propose une taxonomie. Il présente une analyse de la littérature des systèmes tactiles multipoints dans des contextes musicaux. Les concepts de métaphore et d'intégration conceptuelle (blending) sont étudiés puis appliqués à la conception de notre plate-forme de programmation musicale tactile multi-points, TactoSonix.

Nowadays Kademlia is one of the most widely used DHTs (Distributed Hash Table) in P2P (peer-to-peer) networks. This work studies one essential question about Kademlia overlay networks from a mathematical perspective: how long does it take to locate a node? To answer it, we introduce a random graph K to model a Kademlia overlay and study how long it takes to locate a given vertex in K by using Kademlia's routing algorithm. / Aujourd'hui Kademlia est l'un des les plus utilisés DHTs (Distributed Hash Tableau) dans les réseaux P2P (peer-to-peer). Cet article étudie une question essentielle des réseaux "overlay" de Kademlia d'un point de vue mathématique: combien de temps faut-il pour localiser un noeud? Pour y répondre, nous introduisons un graphe aléatoire K pour modéliser un réseau de Kademlia et étudier la complexité d'un algorithme de routage de Kademlia.

Smartphones and similar mobile devices present an unprecedented opportunity to collect data about human behaviour. Integrated into daily life, devices are privy to information about who we communicate with, where we are, and how we spend our time. However, without the proper tools for analysis and the ability to scale up to large amounts of data and large numbers of users, this data is of limited value. This thesis presents tools for extracting information about activities and location from sensor data available on commodity smartphones. We present an algorithm for comparing time series and demonstrate on a large number of benchmark problems that it is competitive with, and often exceeds, the performance of existing algorithms, while being efficient enough to run in real time on a standard smartphone. Activity and gait recognition are presented as applications of our approach, and the performance on these tasks is shown to exceed that of state-of-the-art approaches. For location detection, we present a thorough study of wifi signals in dynamic, nonstationary environments, and conclude that a new multinomial model is preferable to the standard Gaussian model used to model wifi measurements on a mobile terminal. We present a clustering algorithm for wifi signals that uses an underlying multinomial model, and demonstrate on a large dataset that this approach performs favourably on the task of identifying physical locations from wifi data. By basing our approach on the hierarchical Dirichlet process, the number of identifiable locations scales based on the data, and does not need to be prespecified. This allows for accurate, real-time localization of a mobile device both indoors and outdoors, in a manner that, contrary to existing approaches, protects the privacy of the user. Even detailed information is of limited value without the ability to convey it to the user in a meaningful way. We present a framework for translating from sensor data into human-readable descriptions of the events taking place. This framework is evaluated on a corpora of 150 GB of sensor data recorded from 38 users over 14 months, and provides for convenient visualization of large amounts of data and accurate reporting, in natural language, of events transpiring in the data. / Les téléphones intelligents et les appareils mobiles semblables nous fournissent une occasion sans précédent de recueillir des données à propos du comportement humain. Puisqu'ils font partie intégrante de notre vie quotidienne, ces appareils ont accès à des informations privilégiées concernant les personnes avec qui nous communiquons, les endroits où nous nous trouvons, et les façons dont nous passons notre temps. Cependant, sans outils d'analyse adéquats et la capacité de traiter de grandes quantités de données et de grands nombres d'usagers, ces données ont une valeur limitée. Cette thèse présente des outils capables d'extraire des informations concernant les activités et l'emplacement d'une personne à partir des données amassées par les capteurs intégrés dans les téléphones intelligents de consommation courante. Nous présentons un algorithme de comparaison de séries temporelles et nous démontrons que sur un grand nombre de problèmes de référence, la performance de cet algorithme est comparable, et souvent supérieure, à celle des approches de pointe alors que l'algorithme est suffisamment efficace pour être éxécuté en temps réel sur un téléphone intelligent moyen. Nous présentons la reconnaissance des activités et de la démarche en tant qu'applications de cet algorithme, et démontrons que sa performance sur ces tâches dépasse celle des approches de pointe. Concernant la détection de l'emplacement, nous présentons une étude approfondie des signaux wifi dans des environnements dynamiques non-stationnaires, et concluons qu'un nouveau modèle multinomial est préférable au modèle gaussien standard utilisé pour modéliser les mesures de la force des signaux wifi sur un terminal mobile. Nous présentons un algorithme de groupement pour signaux wifi qui utilise un modèle multinomial sous-jacent, et démontrons que sur un ensemble de données de grande taille, la performance de cette approche se compare favorablement à celle du modèle Gaussien standard lorsque qu'elle est confrontée à la tâche d'identifier des emplacements physiques à partir de données wifi. En basant notre approche sur le processus hiérarchique de Dirichlet, le nombre d'emplacements identifiables varie en se basant sur les données, et n'a pas besoin d'être spécifié au préalable. Ceci permet de localiser un appareil mobile en temps réel de façon précise, à l'intérieur comme à l'extérieur, d'une façon qui, contrairement aux approches existantes, protège la vie privée de l'usager. Même les informations détaillées ont une valeur limitée si on ne dispose pas de la capacité de les communiquer à l'usager de façon significative. Nous présentons donc un cadre pour traduire les données amassées par les capteurs en descriptions des évènements qui se produisent lisibles par les êtres humains. Ce cadre est évalué sur des corpora d'une taille combinée de 150 Go composé de données amassées par les capteurs de 38 usagers sur une période de 14 mois, et il permet de visualiser de larges quantités de données ainsi que de produire des rapports exacts, en langage naturel, des évènements dont la trace est extraite des données.

Modern information systems, consisting of an application server tier and a database tier, offer several consistency guarantees for accessing data where strong consistency is traded for better performance or higher availability. However, it is often not clear how an application is affected when it runs under a low level of consistency. In fact, current application designers have basically no tools that would help them to get a feeling of which and how many inconsistencies actually occur during run-time of their particular application. In this thesis, we present new approaches to detect and quantify consistency anomalies for arbitrary multi-tier or cloud applications accessing various types of data stores in transactional or non-transactional contexts. We do not require any knowledge on the business logic of the studied application nor on its selected consistency guarantees. Our detection approaches can be off-line or on-line and for each detected anomaly, we identify exactly the requests and data items involved. Furthermore, we classify the detected anomalies into patterns showing the business methods involved as well as their occurrence frequency. Our approaches can help designers to either choose consistency guarantees where the anomalies do not occur or to change the application design to avoid the anomalies. Furthermore, we provide an option in which future anomalies are dynamically prevented should a certain threshold of anomalies occur. To test the effectiveness of our approaches, we have conducted a set of experiments analyzing the occurrence of anomalies in the benchmarks RUBiS and SPECj Enterprise 2010 under the multi-tier platform JavaEE and the benchmarks JMeter andYahoo! YCSB under the cloud platforms Google App Engine and Cassandra, respectively. / Les systèmes d'information modernes, consistant d'un niveau de serveur d'applications et d'un niveau de base de données, offrent plusieurs guaranties de consistance pour accéder à des données où la consistance est compromise pour une meilleure performance ou pour une haute disponibilité. Cependant, il n'est souvent pas claire comment une application est affectée lorsqu'elle s'exécute sous un bas niveau de consistance. En effet, les concepteurs d'applications actuelles ne disposent pas d'outils qui leur permettent d'avoir un de idée sur quelles inconsistances ainsi que sur leur nombre d'occurence during l'execution de leur application particulière. Dans cette thèse, nous présentons de nouvelles approches pour détecter et quantifier les anomalies de consistance pour des applications arbitraires multi-niveaux ou cloud accédant différent types de bases de données sous des contextes transactionels ou non-transactionels. Nous ne nécessitons aucune connaissance sur la logique de l'application étudiée ni sur ses guaranties de consistance. Notre approche de détection peut êetre hors ligne ou en ligne et pour chaque anomalie détectée, nous identifions exactement les requêetes et les éléments de données impliquées. En outre, nous classons les anomalies détectées en des patrons d'anomalies montrant les méthodes impliquées ainsi que leur fréquence d'occurrence. Notre approche peut aider les concepteurs à choisir soit des garanties de consistance sous lesquelles les anomalies ne se produisent pas ou modifier la conception de leur applications afin d'éviter les anomalies. En outre, nous fournissons une option sous laquelle les futures anomalies sont dynamiquement évitées si un certain seuil d'anomalies est dépassé. Pour tester l'efficacité de nos approches, nous avons mené une série d'expériences analysant l'occurrence d'anomalies pour les bancs d'essai RUBiS et SPECj Enterprise 2010 sous la plate-forme multi-niveaux JavaEE ainsi que pour les bancs d'essai JMeter etYahoo! YCSB respectivement sous les plates-formes cloud Google App Engine et Cassandra.

Reference documentation is an important source of information on API usage. Programmers, however, can easily overlook reference information because of its tedious nature, and because the information they seek can be buried among irrelevant or boiler-plate text. We propose to detect and recommend fragments of API documentation relevant and important to a task. We categorize pieces of information in API documentation based on the type of knowledge they contain. From the pieces that contain knowledge worthy of recommendation, we extract the composition and the pattern of words, and use the patterns to automatically find new pieces that contain similar knowledge. In an evaluation study, with a training set of manually-classified reference documentation of about 1 000 API elements, we could issue recommendations with about, on average, 90% precision and 69% recall. / La documentation de référence est une source importante d'information sur l'usage d'une API. Cependant, les programmeurs peuvent négliger cette information que l'information recherchée se trouve enfouie au milieu de texte passe-partout et sans pertinence. Nous proposons de détecter et recommender les fragments de documentation d'API pertinents à une tâche donnée de façon automatique. Nous catégorisons les morceaux d'information dans la documentation d'API en fonction du type de savoir qu'ils renferment. À partir des morceaux de savoir digne de recommendation, nous extrayons des patrons de mots, puis utilisons ces patrons pour trouver automatiquement de nouveaux morceaux qui renferment un savoir similaire. Nous présentons les résultats d'une évaluation expérimentale de notre système effectuée à partir de plus de 1 000 morceaux d'API, où nous trouvons que notre système offre de recommendations adéquates 90% du temps avec un taux de rappel de 69%.

Internet applications have recently witnessed tremendous growth in terms of both size and complexity. Cloud computing is one of the several distributed technologies that have emerged to help meeting the objectives of these applications in terms of achieving high availability, performance and scalability.Platform as a Service (PaaS) is one kind of services provided by cloud solutions. These systems often follow a multi-tier architecture consisting mainly of a presentation tier, an application tier and a database tier. The volumes of data exchanged between the application tier and the database tier become huge, especially for enterprise level applications. As a result, the design of the database tier in cloud systems has to carefully address the scalability challenges rising from the huge data volumes. In this thesis, we propose a data distribution approach to improve the scalability of the database tier. Our approach is applied to a traditional single database server. It works by replacing the traditionally used single machine storage paradigm with a distributed storage paradigm. The suggested approach maintains the features that originally exists in the database system, and additionally provides the features of distribution and replication. Distributing the data storage helps improving the system fault-tolerance as it decreases the possibility of having a failure at the database server. It also helps resolve specific performance issues such as reducing the I/O usage and consecutively decreasing the possibility of an I/O bottleneck. Yet, it produces other performance challenges that need to be addressed. To prove the feasibility of our proposed approach, we use it to implement two extensions to the storage manager module of the PostgreSQL database system, using the HDFS distributed file system, and the HBase distributed key-value store. / Les applications Internet ont récemment connu une croissance considérable en termes de taille et de complexité. Afin de satisfaire la forte demande pour les ressources informatiques et les espaces de stockage, les technologies en distribution ont commencé à devenir plus impliquées dans les applications à grande échelle. Le Cloud Computing est l'une de ces nombreuses technologies qui ont émergé pour aider à atteindre les objectifs de ces applications, telles que la haute disponibilité, les performances et l'évolutivité.Platform as a Service (PaaS) est un type de service qui peut être fourni par les solutions de Cloud Computing. Ces systèmes suivent souvent une architecture multi-niveaux qui se compose principalement d'un niveau de présentation, un niveau d'application et d'un niveau de base de données. Les volumes de données échangées entre l'application et la base de données deviennent énormes en particulier pour les applications de niveau entreprise. En conséquence, la conception de la base de données dans les systèmes de Cloud Computing doit prendre en compte le challenge de l'évolution des quantités énormes de données. Dans cette mémoire, nous proposons une approche de distribution des données qui peuvent être utilisées pour améliorer l'évolutivité des bases de données. Nous proposons deux techniques qui peuvent être appliquées à un serveur de base de données unique traditionnelle.Ces techniques fonctionnent en remplaçant le paradigme traditionnel utilisant une seule machine de stockage avec un paradigme de stockage distribué. Les techniques proposées maintiennent les caractéristiques qui existaient à l'origine dans le système de base de données, et en plus fournissent les caractéristiques de la distribution et de la réplication. Ces deux fonctionnalités supplémentaires aident à améliorer le système de tolérance aux pannes, car ils diminuent la possibilité d'avoir une défaillance au niveau du serveur de base de données. La distribution du stockage permet de résoudre les problèmes de performances spécifiques, tels que la réduction de l'utilisation des entrées/sorties et consécutivement de diminuer la possibilité de saturation des entrées/sorties.Par ailleurs, cela produit d'autres défis de performances qui doivent être pris en compte. Pour prouver la faisabilité de nos techniques, nous les avons implémentées comme des extensions du module de gestion de stockage de la base de données PostgreSQL.