Au vu des dernières avancées dans le domaine de l’ingénierie web, ainsi qu’avec la baisse de coût du cloud computing, les architectures orientées services sont rapidement devenues la solution prépondérante pour fournir des services à valeur ajoutée aux clients. Suite à cette tendance, la composition de services tiers est devenue un paradigme de référence pour le développement d’applications robustes et riches, ou encore pour l’automatisation de processus métiers. Avec la disponibilité de centaines de milliers de services et APIs web, la réalisation de telles intégrations devient lourde et fastidieuse quand effectuée manuellement. Par ailleurs, chaque client peut exiger des besoins et politiques d’intégration différentes, ce qui complexifie davantage la tâche. De plus, fournir une telle solution qui soit à la fois robuste et scalable est une tâche non-triviale. Il est donc primordial d’étudier comment coordonner de manière efficace les interactions entre les services web existants. Ainsi, cette thèse vise à étudier les problématiques liées à la composition de services web dans le contexte des pratiques de développement web modernes. Nous présentons un cadre architectural permettant la spécification de compositions de services web grâce à une approche orientée langage, et montrons comment supporter leur exécution de manière scalable grâce à MEDLEY, une plateforme légère et orientée événements. / In light of the recent advances in the field of web engineering, along with the decrease of cost of cloud computing, service-oriented architectures rapidly became the leading solution in providing valuable services to clients. Following this trend, the composition of third-party services has become a successful paradigm for the development of robust and rich distributed applications, as well as automating business processes. With the availability of hundreds of thousands of web services and APIs, such integrations become cumbersome and tedious when performed manually. Furthermore, different clients may require different integration requirements and policies, which further complexifies the task. Moreover, providing such a solution that is both robust and scalable is a non-trivial task. Therefore, it becomes crucial to investigate how to efficiently coordinate the interactions between existing web services. As such, this thesis aims at investigating the underlying challenges in web service composition in the context of modern web development practices. We present an architectural framework to support the specification of web service compositions using a language-based approach, and show how we support their execution in a scalable manner using MEDLEY, a lightweight, event-driven platform.

Les systèmes distribués sont de plus en plus grands et complexes, alors que leur utilisation s'étend à de nombreux domaines (par exemple, les communications, la domotique, la surveillance, le ``cloud''). Par conséquent, les contextes d'exécution des systèmes distribués sont très divers. Dans cette thèse, nous nous focalisons sur des contextes incertains, autrement dit, le contexte n'est pas complètement connu au départ ou il est changeant. Plus précisément, nous nous focalisons sur deux principaux types d'incertitudes : une identification incomplète des processus et la présence de fautes. L'absence d'identification est fréquente dans de grands réseaux composés d'appareils produits et déployés en masse. De plus, l'anonymat est souvent une demande pour la sécurité et la confidentialité. De la même façon, les grands réseaux sont exposés aux pannes comme la panne définitive d'un processus ou une perte de connexion sans fil. Néanmoins, le service fourni doit rester disponible.Cette thèse est composée de quatre contributions principales. Premièrement, nous étudions le problème de l'élection de leader dans les anneaux unidirectionnels de processus homonymes (les processus sont identifiés mais leur ID n'est pas forcément unique). Par la suite, nous proposons un algorithme d'élection de leader silencieux et autostabilisant pour tout réseau connecté. Il s'agit du premier algorithme fonctionnant sous de telles conditions qui stabilise en un nombre polynomial de pas de calcul. La troisième contribution est une nouvelle propriété de stabilisation conçue pour les réseaux dynamiques qui garantit des convergences rapides et progressives après des changements topologiques. Nous illustrons cette propriété avec un algorithme de synchronisation d'horloges. Finalement, nous considérons la question de la concurrence dans les problèmes d'allocation de ressources. En particulier, nous étudions le niveau de concurrence qui peut être atteint dans une grande classe de problèmes d'allocation de ressources, l'allocation de ressources locales. / Distributed systems become increasingly wide and complex, while their usage extends to various domains (e.g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i.e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e.g, process crashes, wireless connection drop), but the service must remain available.This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i.e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i.e., the local resource allocation.

L’agrégation des valeurs qui doivent être gardées confidentielles tout en garantissant la robustesse du processus et l’exactitude du résultat est nécessaire pour un nombre croissant d’applications. Divers types d’enquêtes, telles que les examens médicaux, les référendums, les élections, ainsi que les nouveaux services de Internet of Things, tels que la domotique, nécessitent l’agrégation de données confidentielles. En général,la confidentialité est assurée sur la base de tiers de confiance ou des promesses de cryptographie, dont les capacités ne peuvent être évaluées sans expertise.L’ambition de cette thèse est de réduire le besoin de confiance dans les autorités, de même que la technologie, et d’explorer les méthodes d’agrégations de données à grande échelle, qui garantissent un degré élevé de confidentialité et ne dépendent ni de tiers de confiance ni de cryptographie. Inspiré par BitTorrent et Bitcoin, les protocoles P2P sont considérés. La première contribution de cette thèse est l’extension du protocole d’agrégation distribuée BitBallot dans le but de couvrir les agrégations dans les réseaux P2P comprenant des pairs adversaires avec un comportement défaillant ou byzantin. Les changements introduits permettent éventuellement de maintenir un résultat précis en présence d’une minorité adversaire. Les limites de scalabilité rencontrées conduisent à la deuxième contribution dans le but de soutenir les agrégations à grande échelle. Inspiré par BitBallot et BitTorrent, un nouveau protocole distribué appelé ADVOKAT est proposé.Dans les deux protocoles, les pairs sont affectés aux noeuds feuilles d’un réseau de superposition d’une structure arborescente qui détermine le calcul des agrégats intermédiaires et restreint l’échange de données. La partition des données et du calcul entre un réseau de pairs équipotent limite le risque de violation de données et réduit le besoin de confiance dans les autorités. Les protocoles fournissent une couche middleware dont la flexibilité est démontrée par les applications de vote et de loterie. / Aggregation of values that need to be kept confidential while guaranteeing the robustness of the process and the correctness of the result is necessary for an increasing number of applications. Various kinds of surveys, such as medical ones, opinion polls, referendums, elections, as well as new services of the Internet of Things, such as home automation, require the aggregation of confidential data. In general, the confidentiality is ensured on the basis of trusted third parties or promises of cryptography, whose capacities cannot be assessed without expert knowledge.The ambition of this thesis is to reduce the need for trust in both authorities and technology and explore methods for large-scale data aggregations, that ensure a high degree of confidentiality and rely neither on trusted third parties nor solely on cryptography. Inspired by BitTorrent and Bitcoin, P2P protocols are considered.The first contribution of this thesis is the extension of the distributed aggregation protocol BitBallot with the objective to cover aggregations in P2P networks comprising adversarial peers with fail-stop or Byzantine behaviour. The introduced changes allow eventually to maintain an accurate result in presence of an adversarial minority.The encountered scalability limitations lead to the second contribution with the objective to support large-scale aggregations. Inspired by both BitBallot and BitTorrent, a novel distributed protocol called ADVOKAT is proposed.In both protocols, peers are assigned to leaf nodes of a tree overlay network which determines the computation of intermediate aggregates and restricts the exchange of data. The partition of data and computation among a network of equipotent peers limits the potential for data breaches and reduces the need for trust in authorities. The protocols provide a middleware layer whose flexibility is demonstrated by voting and lottery applications.

Les microrobots MEMS sont des éléments miniaturisés qui peuvent capter et agir sur l'environnement. Leur taille est de l'ordre du millimètre et ils ont une faible capacité de mémoire et une capacité énergétique limitée. Les microrobots MEMS continuent d'accroître leur présence dans notre vie quotidienne. En effet, ils peuvent effectuer plusieurs missions et tâches dans une large gamme d'applications telles que la localisation d'odeur, la lutte contre les incendies, le service médical, la surveillance, le sauvetage et la sécurité. Pour faire ces taches et missions, ils doivent appliquer des protocoles de redéploiement afin de s'adapter aux conditions du travail. Ces algorithmes doivent être efficaces, évolutifs, robustes et ils doivent utiliser de préférence des informations locales. Le redéploiement pour les microrobots MEMS mobiles nécessite actuellement un système de positionnement et une carte (positions prédéfinies) de la forme cible. La solution traditionnelle de positionnement comme l'utilisation d'un GPS consommerait trop d'énergie. De plus, l'utilisation de solutions de positionnement algorithmique avec les techniques de multilatération pose toujours des problèmes à cause des erreurs dans les coordonnées obtenues.Dans la littérature, si nous voulons une auto-reconfiguration de microrobots vers une forme cible constituée de P positions, chaque microrobot doit avoir une capacité mémoire de P positions pour les sauvegarder. Par conséquent, si P est de l'ordre de milliers ou de millions, chaque noeud devra avoir une capacité de mémoire de positions en milliers ou millions. Parconséquent, ces algorithmes ne sont pas extensibles ou évolutifs. Dans cette thèse, on propose des protocoles de reconfiguration où les noeuds ne sont pas conscients de leurs positions dans le plan et n'enregistrent aucune position de la forme cible. En d'autres termes, les noeuds ne stockent pas au départ les coordonnées qui construisent la forme cible. Par conséquent, l'utilisation de mémoire pour chaque noeud est réduite à une complexité constante. L'objectif desalgorithmes distribués proposés est d'optimiser la topologie logique du réseau des microrobots afin de chercher une meilleure complexité pour l'échange de message et une communication peu coûteuse. Ces solutions sont complètement distribués. On montre pour la reconfiguration d'une chaîne à un carré comment gérer la dynamicité du réseau pour sauvegarder l'énergie, on étudie comment utiliser le parallélisme de mouvements pour optimiser le temps d'exécution et lenombre de mouvements. Ainsi, on propose une autre solution où la topologie physique initiale peut être n'importe quelle configuration initiale. Avec ces solutions, les noeuds peuvent exécuter l'algorithme indépendamment du lieu où ils sont déployés, parce que l'algorithme est indépendant de la carte de la forme cible. En outre, ces solutions cherchent à atteindre la forme de la cible avec une quantité minimale de mouvement. / MEMS microrobots are miniaturized elements that can capture and act on the environment. They have a small size, low memory capacity and limited energy capacity. These inexpensive devices can perform several missions and tasks in a wide range of applications such as locating odor, fighting against fires, medical service, surveillance, search, rescue and safety. To do these tasks and missions, they have to carry out protocols of redeployment to adapt to the working conditions. These algorithms should be efficient, scalable, robust and should only use local information. Redeployment for mobile MEMS microrobots currently requires a positioning system and a map (predefined positions) of the target shape. Traditional positioning solutions such as using GPS consumes a lot of energy and it is no applicable in the micro scale. Also, the use of an algorithmic solution positioning with multilateration techniques causes problems due to errors in the coordinates obtained. In the literature works, if we want a microrobots self-reconfiguring to a target shape consisting of P positions, each microrobot must have a storage capacity of at least P positions to save them. Therefore, if P equals to thousands or millions, every node must have a storage capacity of thousands or millions of positions. However, these algorithms are notscalable. In this thesis, we propose protocols of self-reconfiguration where nodes are not aware of their position in the plane and do not record the positions of the target shape. Therefore, the memory space required for each node is significantly reduced at a constant complexity. The purpose of these distributed algorithms is to optimize the logical topology of the network of mobile MEMS microrobots to seek a better complexity for message exchange and inexpensive communication.In this work, we show for the reconfiguration of a chain into a square, how to handle the dynamicity of the network to save energy, and we study how to use parallelism in motion to optimize the execution time and the number of movements. Furthermore, another solution is proposed where the initial physical topology may be any connected configuration. With thesesolutions the nodes can execute the algorithm regardless of where they are deployed, because the algorithm is independent of the map of the target shape. Furthermore, these solutions seek to achieve the shape of the target with a minimum amount of movement.

Les réseaux MANET représentent un domaine important de recherche en raison des nombreuses opportunités découlant des problématiques et des applications inhérentes à ce type de réseau. Les problématiques les plus récurrentes sont la mobilité, la disponibilité ainsi que les ressources limitées. Un intérêt bien connu dans les réseaux et donc dans les MANET est de monitorer les propriétés de ce réseau et de ses nœuds. Les contraintes des MANET peuvent avoir un impact significatif sur les efforts mis en œuvre pour les monitorer. La mobilité et la disponibilité peuvent créer des résultats incomplets pour le monitorage. Les propriétés usuelles utilisées en monitorage sont simples, comme notamment la consommation moyenne du processeur, la bande passante moyenne, etc. De plus, l'évolution des réseaux a conduit à un besoin croissant d'examiner des comportements plus complexes, dépendants et imbriqués. La littérature indique que la précision des valeurs obtenues par monitorage et donc des approches n'est pas fiable et difficile à atteindre en raison des propriétés dynamiques du MANET. Nous proposons donc des architectures de surveillance décentralisées et distribuées qui reposent sur de multiples points d'observation. L'approche décentralisée combine des algorithmes dits hiérarchiques et de ‘gossip’ pour fournir une approche de monitorage efficace. Grâce à des expérimentations approfondies, nous avons conclu que même si nous étions en mesure d'atteindre d’excellentes performances, la fragmentation du réseau a toujours un impact sévère sur la méthodologie mise en place. Essayant d'améliorer notre technique, nous avons proposé une approche distribuée pour améliorer l'efficacité et la précision globale.Il fournit un mécanisme de consensus qui lui permet d'agréger de nombreux résultats fournis par plusieurs nœuds et fournit un résultat plus significatif et plus précis. Nous soutenons notre proposition avec de nombreuses définitions mathématiques qui modélisent les résultats locaux pour un seul nœud et les résultats globaux pour le réseau. Nos expériences ont été évaluées avec un émulateur construit en interne qui s'appuie sur Amazon Web Services, NS-3, Docker et GoLang avec un nombre variable de nœuds, la taille du réseau, sa densité, la vitesse des nœuds, les algorithmes de mobilité et les délais. Grâce à cet émulateur, nous avons pu analyser plusieurs aspects en fournissant des testbeds reproductibles, documentés et accessibles. Nous avons obtenu des résultats prometteurs pour les deux approches, et surtout pour l'approche distribuée en particulier en ce qui concerne la précision des valeurs obtenues par monitorage / MANETs represent a significant area of network research due to the many opportunities derived from the problematics and applications. The most recurring problematics are the mobility, the availability and also the limited resources. A well-known interest in networks and therefore in MANETs is to monitor properties of the network and nodes. The problematics of the MANETs can have a significant impact on the monitoring efforts. Mobility and availability can create incomplete results for the monitoring. The usual properties discussed in monitoring are simple ones, e.g., average CPU consumption, average bandwidth and so on. Moreover, the evolution of networks has led to an increasing need to examine more complex, dependent and intertwined behaviors. The literature states that accuracy of the approaches is not reliable and difficult to achieve due to the dynamic properties of the MANET. Therefore, we propose a decentralized and distributed monitoring architecture that rely on multiple points of observation. The decentralized approach combines gossip and hierarchical algorithms to provide an effective monitoring approach. Through extensive experimentation, we concluded that although we were able to achieve exceptional performance, network fragmentation still has a harsh impact on the approach. Trying to improve our approach, we proposed a distributed approach, relying on stronger bedrock to enhance the overall efficiency and accuracy. It provides a consensus mechanism that allows it to aggregate and provides a more meaningful and accurate result. We support our proposal with numerous mathematical definition that models local results for a single node and global results for the network. Our experiments were evaluated with an emulator built in-house that relies on Amazon Web Services, NS-3, Docker and GoLang with varying number of nodes, network size, network density, speed, mobility algorithms and timeouts. Through this emulator, we were able to analyze multiple aspects of the approaches by providing a repeatable, documented and accessible test beds. We obtained promising results for both approaches, but for the distributed approach, especially regarding accuracy

Les systèmes informatiques impliquant la détection d’anomalies émergent aussi bien dans le domaine de la recherche que dans l'industrie. Ainsi, des domaines aussi variés que la médecine (identification de tumeurs malignes), la finance (détection de transactions frauduleuses), les technologies de l’information (détection d’intrusion réseau) et l'environnement (détection de situation de pollution) sont largement impactés. L’apprentissage automatique propose un ensemble puissant d'approches qui peuvent aider à résoudre ces cas d'utilisation de manière efficace. Cependant, il représente un processus lourd avec des règles strictes qui supposent une longue liste de tâches telles que l'analyse et le nettoyage de données, la réduction des dimensions, l'échantillonnage, la sélection des algorithmes, l'optimisation des hyper-paramètres, etc. Il implique également plusieurs experts qui travailleront ensemble pour trouver les bonnes approches. De plus, les possibilités ouvertes aujourd'hui par le monde de la sémantique montrent qu'il est possible de tirer parti des technologies du web afin de raisonner intelligemment sur les données brutes pour en extraire de l'information à forte valeur ajoutée. L'absence de systèmes combinant les approches numériques d'apprentissage automatique et les techniques sémantiques du web des données constitue la motivation principale derrière les différents travaux proposés dans cette thèse. Enfin, les anomalies détectées ne signifient pas nécessairement des situations de réalité anormales. En effet, la présence d'informations externes pourrait aider à la prise de décision en contextualisant l'environnement dans sa globalité. Exploiter le domaine spatial et les réseaux sociaux permet de construire des contextes enrichis sur les données des capteurs. Ces contextes spatio-temporels deviennent ainsi une partie intégrante de la détection des anomalies et doivent être traités en utilisant une approche Big Data. Dans cette thèse, nous présentons trois systèmes aux architectures variées, chacun ayant porté sur un élément essentiel des écosystèmes big data, temps-réel, web sémantique et apprentissage automatique : WAVES : Plateforme Big Data d'analyse en temps réel des flux de données RDF capturées à partir de réseaux denses de capteurs IoT. Son originalité tient dans sa capacité à raisonner intelligemment sur des données brutes afin d'inférer des informations implicites à partir d'informations explicites et d'aider dans la prise de décision. Cette plateforme a été développée dans le cadre d'un projet FUI dont le principal cas d'usage est la détection d'anomalies dans un réseau d'eau potable. RAMSSES : Système hybride d'apprentissage automatique dont l'originalité est de combiner des approches numériques avancées ainsi que des techniques sémantiques éprouvées. Il a été spécifiquement conçu pour supprimer le lourd fardeau de l'apprentissage automatique qui est chronophage, complexe, source d'erreurs et impose souvent de disposer d'une équipe pluridisciplinaire. SCOUTER : Système intelligent de "scrapping web" permettant la contextualisation des singularités liées à l'Internet des Objets en exploitant aussi bien des informations spatiales que le web des données / Computer systems involving anomaly detection are emerging in both research and industry. Thus, fields as varied as medicine (identification of malignant tumors), finance (detection of fraudulent transactions), information technologies (network intrusion detection) and environment (pollution situation detection) are widely impacted. Machine learning offers a powerful set of approaches that can help solve these use cases effectively. However, it is a cumbersome process with strict rules that involve a long list of tasks such as data analysis and cleaning, dimension reduction, sampling, algorithm selection, optimization of hyper-parameters. etc. It also involves several experts who will work together to find the right approaches. In addition, the possibilities opened today by the world of semantics show that it is possible to take advantage of web technologies to reason intelligently on raw data to extract information with high added value. The lack of systems combining numeric approaches to machine learning and semantic techniques of the web of data is the main motivation behind the various works proposed in this thesis. Finally, the anomalies detected do not necessarily mean abnormal situations in reality. Indeed, the presence of external information could help decision-making by contextualizing the environment as a whole. Exploiting the space domain and social networks makes it possible to build contexts enriched with sensor data. These spatio-temporal contexts thus become an integral part of anomaly detection and must be processed using a Big Data approach.In this thesis, we present three systems with different architectures, each focused on an essential element of big data, real-time, semantic web and machine learning ecosystems:WAVES: Big Data platform for real-time analysis of RDF data streams captured from dense networks of IoT sensors. Its originality lies in its ability to reason intelligently on raw data in order to infer implicit information from explicit information and assist in decision-making. This platform was developed as part of a FUI project whose main use case is the detection of anomalies in a drinking water network. RAMSSES: Hybrid machine learning system whose originality is to combine advanced numerical approaches as well as proven semantic techniques. It has been specifically designed to remove the heavy burden of machine learning that is time-consuming, complex, error-prone, and often requires a multi-disciplinary team. SCOUTER: Intelligent system of "web scrapping" allowing the contextualization of singularities related to the Internet of Things by exploiting both spatial information and the web of data

Les transports terrestres occupent une place majeure dans notre société, notamment en ville où les ralentissements aux heures de pointe peuvent avoir un impact notable sur l'organisation des activités, l'économie ou encore l'écologie. Les infrastructures routières sont généralement coordonnées par un centre de contrôle, responsable du maintien des équipements, de leurs réglages initiaux et de la gestion des incidents (matériels ou humains). Les nouvelles technologies de l'information et de la communication ont permis, en l'espace de quelques années, de mettre en œuvre des systèmes de transport intelligents. À l'aide de multiples points de mesures répartis sur le territoire, un opérateur peut dénombrer les usagers et en déduire la charge du réseau. Toutefois, centraliser les informations présente de nombreuses limites. Cette thèse vise à étudier l'emploi de systèmes distribués afin de mettre en œuvre des systèmes de transport intelligents grâce à un réseau de capteurs sans fil. Couplés à une unité de détection (p. ex., un magnétomètre), les capteurs communicants peuvent réagir au passage d'un véhicule en étant déployés, par exemple, sur les voies. Ils sont également capables de coopérer et de s'affranchir d'une entité centrale, rendant tout ou partie d'une zone urbaine totalement indépendante. D'autre part, ces réseaux peuvent fonctionner de manière autonome et tolèrent mieux les pannes, car aucun élément n'est indispensable au fonctionnement global du système. Enfin, les éléments de ces réseaux sont petits, peu coûteux, et communiquent en sans fil, ce qui leur permet d'être déployés et redéployés rapidement et de manière dense. / Road traffic has a significant effect on metropolitan activities, especially during peak hours when it impacts on areas such as the economy and the environment. Road infrastructure is typically coordinated from a control centre that is responsible for maintaining not only its equipment but also their initial settings and incident management (both material and human). During the past few years, new technologies in the fields of information and communication have led to the introduction of intelligent transportation systems. Using multiple measurement points distributed across a country, an operator can count road users and calculate the network load. However, the centralization of information has a number of drawbacks. The aim of this thesis is to study the use of distributed systems in order to implement intelligent transportation systems via a wireless sensor network. Coupled to a detection unit (e.g., a magnetometer), the interconnected sensors can respond to the passage of a vehicle when deployed, for example, along the road. They can also work together without recourse to a central entity - rendering all or part of an urban area totally independent. Furthermore, these networks can operate autonomously and are less susceptible to breadown, because the overall running of the system is not affected by the failure of individual components. Finally, components are small and cheap, and they operate wirelessly, which means they can be deployed and redeployed both rapidly and densely.

La dissémination collaborative d'une information d'un agent à tous les autres agents d'un système distribué est un problème fondamental qui est particulièrement important lorsque l'on veut obtenir des algorithmes distribués qui sont à la fois robustes et fonctionnent dans un cadre anonyme, c'est-à-dire sans supposer que les agents possèdent des identifiants distincts connus. Ce problème, connu sous le nom de problème de propagation de rumeur , est à la base de nombreux algorithmes de communication sur des réseaux de capteurs sans-fil [Dimakis et al. (2010)] ou des réseaux mobiles ad-hoc. Il est aussi une brique de base centrale pour de nombreux algorithmes distribués avancés [Mosk-Aoyama et Shah (2008)].Les méthodes les plus connues pour surmonter les défis de robustesse et d'anonymat sont les algorithmes basés sur les ragots ( gossip-based algorithms ), c'est-à-dire sur la paradigme que les agents contact aléatoirement les autres agents pour envoyer ou récupérer l'information. Nousproposons une méthode générale d'analyse de la performance des algorithmes basés sur les ragots dans les graphes complets. Contrairement aux résultats précédents basés sur la structure précise des processus étudiés, notre analyse est basée sur la probabilité et la covariance des évènements correspondants au fait qu'un agent non-informé s'informe. Cette universalité nous permet de reproduire les résultats basiques concernant les protocoles classiques de push, pull et push-pull ainsi qu'analyser les certaines variantions telles que les échecs de communications ou les communications simultanés multiples réalisées par chaque agent. De plus, nous sommescapables d'analyser les certains modèles dynamiques quand le réseaux forme un graphe aléatoire échantillonné à nouveau à chaque étape [Clementi et al. (ESA 2013)]. Malgré sa généralité, notre méthode est simple et précise. Elle nous permet de déterminer l'espérance du temps de la diffusion à une constante additive près, ce qu'il est plus précis que la plupart des résultatsprécédents. Nous montrons aussi que la déviation du temps de la diffusion par rapport à son espérance est inférieure d'une constante r avec la probabilité au moins 1 − exp(Ω(r)).À la fin, nous discutons d'une hypothèse classique que les agents peuvent répondre à plusieurs appels entrants. Nous observons que la restriction à un seul appel entrant par agent provoque une décélération importante du temps de la diffusion pour un protocole de push-pull. En particulier, une phase finale du processus prend le temps logarithmique au lieu du temps double logarithmique. De plus, cela augmente le nombre de messages passés de Θ(n log log n) (valeur optimale selon [Karp et al. (FOCS 2000)]) au Θ(n log n) . Nous proposons une variation simple du protocole de push-pull qui rétablit une phase double logarithmique à nouveau et donc le nombre de messages passés redescend sur sa valeur optimal. / Epidemic algorithms are distributed algorithms in which the agents in thenetwork involve peers similarly to the spread of epidemics. In this work, we focus on randomized rumor spreading -- a class of epidemic algorithms based on the paradigm that nodes call random neighbors and exchange information with these contacts. Randomized rumor spreading has found numerous applications from the consistency maintenance of replicated databases to newsspreading in social networks. Numerous mathematical analyses of different rumor spreading algorithms can be found in the literature. Some of them provide extremely sharp estimates for the performance of such processes, but most of them are based on the inherent properties of concrete algorithms.We develop new simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as when messages fail with constant probability or when nodes call a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of r rounds occurs with probability at most exp(−Ω(r)).We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal Θ(n log log n) [Karp, Shenker, Schindelhauer, Vöcking (FOCS 2000)] to Θ(n log n). We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the Θ(n log log n) message complexity.

Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans les espaces métriques générés par certains de ces outils, comme Vivaldi et Sequoia.

L'émergence et le développement des systèmes électriques de ces vingt dernières années nous ont conduits à l'élaboration d'architectures de plus en plus complexes. Nous les retrouvons notamment au niveau d'applications embarquées ainsi qu'au cœur de réseaux de distribution isolés. L'intégration de nombreux équipements de différentes natures soulève la problématique de la stabilité. C'est dans ce contexte que s'insèrent ces travaux de thèse, qui aboutissent sur la mise en œuvre de méthodes d'analyse de la stabilité et de la qualité des réseaux distribués de puissance. Les études menées au cours de ces travaux reposent sur des expressions analytiques représentant le comportement fréquentiel de réseaux continus. Ces modèles sont ensuite associés au critère de Routh-Hurwitz, afin de permettre les études de stabilité selon les évolutions de leurs paramètres. L'analyse des résultats obtenus au niveau d'architectures présentant plusieurs équipements permet d'affiner nos connaissances sur le fonctionnement de ces systèmes. Les phénomènes de couplage, la disposition d'un réseau en fonction du nombre et de la puissance des charges, du point de vue de la stabilité, sont notamment développés. Les recherches de dimensionnements optimaux de plusieurs éléments indéterminés, combinant les notions de stabilité et de qualité et réalisées à l'aide d'algorithmes d'optimisation, sont également présentées. Enfin, les parties fondamentales de ces travaux, que constituent la modélisation ainsi que l'étude de la stabilité, sont validés par une approche expérimentale. / The emergence and the development of electrical systems during these last twenty years have led us to the elaboration of more and more complex architectures. They can be particularly found on embedded applications as well as in the heart of isolated distribution networks. The integration of several equipments with various natures raises the problem of stability. Thesis work presented here fits in with this context, leading to the implementation of stability and quality analysis methods, applied to distributed power networks. Studies led during this work are based on analytical expressions representing the continuous networks frequency behaviour. These models are then associated to the Routh-Hurwitz criterion in order to allow stability studies, according to their parameter values evolution. Analysis of results obtained on networks architectures using several equipments allows the refinement of our knowledge on these systems operation. Coupling phenomena, network layout according the loads number and power from a stability point of view, are particularly developed. Optimal sizing research for several undetermined elements, merging stability and quality criteria and carried out using optimization algorithms, is also presented. Finally, fundamental parts of this work which correspond to models building as well as stability studies are validated by an experimental approach.