Il existe de nombreuses méthodes d'optimisation du routage réseau en général. Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation, au sens de Nash, des flux réseaux. Nous rappelons tout d'abord brièvement le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présentons un jeu de tarification simple à deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présentons un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présentons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibres du système. / There are several approaches for optimizing network routing in general. In this document, we are interested in developping distributed algorithms able to stabilize the network flows in the sense of Nash. We introduce the general context of the Internet today along with a few key-notions in game theory. We show a simple two-player tarification game that the fictitious player dynamics is able to solve. Then, we introduce a more complex routing game with n players based on the Wardrop model and a distributed learning algorithm that allows the system to converge towards Wardop equilibria (social equilibrium). These equilibria also are Nash equilibria in the limit case where a player is an infinitesimal part of the network flow. We present a refinement of our initial representation of the problem that narrows down its complexity, in terms of the size of the strategy space and computation time. We show that it is a good heuristic for approximating the previous method, its quality relies upon only one parameter. Finally, we conclude with simulations results, showing that our distributed method is able to learn the best equilibriua of the system.

Cette thèse se place dans le cadre de la modélisation et de l'analyse de systèmes parallèles et répartis. Plus précisément, nous nous intéressons à la modélisation, la vérification et la supervision de systèmes, composés d'entités indépendantes interagissant localement par mémoire partagée et globalement par échange asynchrone de messages.<br /><br />Dans ce contexte, plutôt que de modéliser séparément chaque entité, puis d'analyser les comportements qui peuvent se produire lorsque ces entités interagissent, nous fournissons une théorie permettant de modéliser globalement le système considéré tout en conservant des propriétés de vérification et de supervision décidables. Cette théorie se base sur le formalisme des ordres partiels étiquetés (appelés "pomsets").<br /><br />Dans ce but, nous définissons le modèle des HMSC causaux qui étend le formalisme des HMSC en autorisant, comme pour les traces de Mazurkiewicz, certains événements à commuter sur chaque processus. Nous montrons, tout d'abord, qu'une restriction syntaxique des HMSC causaux a le même pouvoir d'expression que les réseaux bornés d'automates mixtes, un modèle qui étend les réseaux d'automates asynchrones de Zielonka et les réseaux d'automates communicants. De plus, nous montrons que les méthodes classiques de model-checking de systèmes séquentiels peuvent s'appliquer aux modèles plus concis basés sur les pomsets, comme les HMSC causaux, sans perte d'efficacité. Enfin, nous proposons des méthodes de traitement efficace d'observations volumineuses d'exécutions réparties, ainsi que des techniques de supervision, telles que le diagnostic ou la corrélation d'événements, qui utilisent des modèles basés sur les pomsets.

Cette thèse a pour objectif de proposer une démarche pour effectuer l'optimisation des requêtes dans un systeme de bases de données reparties. On énumère l'ensemble de tous les critères d'optimisation qui peuvent être pris en compte et on décide les objectifs d'optimisation. On propose une démarche progressive divisée en plusieurs étapes qui visent aux objectifs d'optimisation : la localisation, les permutations des opérations, l'allocation des données reparties par le regroupement et la distribution des opérations aux processus repartis par le partitionnement.

Cette thèse s'intéresse à la flexibilité dans les infrastructures informatiques distribuées du point de vue de leurs administrateurs et utilisateurs. Pour les utilisateurs, il s'agit de trouver au moment où ils en ont besoin des ressources matérielles adaptées avec un environnement personnalisé à l'exécution de leur application. Pour les administrateurs, il s'agit de définir les politiques d'allocation des ressources (politiques d'usage et de sécurité) pour les applications des utilisateurs. Nous avons étudié la problématique de la flexibilité dans le contexte des grilles et des centrales numériques (CN). Tout d'abord, nous avons conçu et mis en oeuvre le système Saline qui s'appuie sur la virtualisation pour permettre l'exécution de tout type de tâche en mode préemptif dans les grilles. Nous avons également proposé le système Grillade qui combine les mécanismes de flexibilité offerts par les grilles et les CN pour d'une part, étendre dynamiquement une grille avec des ressources virtuelles fournies par des CN et d'autre part, construire des nuages de type IaaS fédérant les ressources de plusieurs sites. Grillade étend le système de grille XtreemOS. Il permet en outre grâce à la technologie de système à image unique de proposer aux utilisateurs des machines virtuelles exécutées sur une agrégation de nœuds. Enfin, nous proposons un formalisme permettant de classer les systèmes de gestion de ressources offrant de la flexibilité et de définir des règles pour les combiner. Le système Tropicbird qui s'appuie sur ce formalisme met en œuvre, à la demande, des plates-formes virtuelles spécifiées par les utilisateurs sur une infrastructure matérielle.

De nos jours, les technologies de l'information offrent aux utilisateurs la possibilité de travailler avec n'importe qui, à n'importe quel moment, de n'importe où et avec plusieurs dispositifs hétérogènes. Cette évolution favorise un nouveau modèle distribué de collaboration de confiance où les utilisateurs peuvent travailler sur des documents partagés avec qui ils ont confiance. La collaboration multi-synchrone est largement utilisée pour soutenir le travail collaboratif en maintenant des flux simultanés de l'activité des utilisateurs qui divergent et convergent continuellement. Cependant, ce modèle n'offre pas de support concernant l'expression et la vérification de restriction d'usage des données. Cette thèse présente C-PPC, un modèle de collaboration basé sur les contrats et sur la confiance. Dans ce modèle, des contrats sont utilisés comme des règles d'utilisation des données et les utilisateurs collaborent en fonction des niveaux de confiance qu'ils attribuent aux autres en accord avec le respect des contrats. Nous formalisons les contrats en utilisant des concepts déontiques: permission, obligation et prohibition. Les contrats sont inclus dans les historiques d'opérations des données partagées. Le modèle C-PPC fournit un mécanisme pour la fusion des modifications des données et des contrats. N'importe quel utilisateur peut auditer les historiques à n'importe quel moment et les résultats de l'audit sont utilisés pour actualiser les niveaux de confiance en se basant sur une métrique de confiance. Nous proposons une solution reposant sur des authentificateurs basés sur les chaînes de hachage pour garantir l'intégrité des historiques et la responsabilité des utilisateurs. Nous fournissons des algorithmes pour construire les authentificateurs et vérifier les historiques puis nous prouvons leur correction. Des résultats expérimentaux montrent la faisabilité du modèle C-PPC.

In this thesis, we propose an approach to achieve autonomous task partitioning in swarms of robots. Task partitioning is the process by which tasks are decomposed into sub-tasks and it is often an advantageous way of organizing work in groups of individuals. Therefore, it is interesting to study its application to swarm robotics, in which groups of robots are deployed to collectively carry out a mission. The capability of partitioning tasks autonomously can enhance the flexibility of swarm robotics systems because the robots can adapt the way they decompose and perform their work depending on specific environmental conditions and goals. So far, few studies have been presented on the topic of task partitioning in the context of swarm robotics. Additionally, in all the existing studies, there is no separation between the task partitioning methods and the behavior of the robots and often task partitioning relies on characteristics of the environments in which the robots operate.<p>This limits the applicability of these methods to the specific contexts for which they have been built. The work presented in this thesis represents the first steps towards a general framework for autonomous task partitioning in swarms of robots. We study task partitioning in foraging, since foraging abstracts practical real-world problems. The approach we propose in this thesis is therefore studied in experiments in which the goal is to achieve autonomous task partitioning in foraging. However, in the proposed approach, the task partitioning process relies upon general, task-independent concepts and we are therefore confident that it is applicable in other contexts. We identify two main capabilities that the robots should have: i) being capable of selecting whether to employ task partitioning and ii) defining the sub-tasks of a given task. We propose and study algorithms that endow a swarm of robots with these capabilities. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

De nos jours, les technologies de l'information offrent aux utilisateurs la possibilité de travailler avec n'importe qui, à n'importe quel moment, de n'importe où et avec plusieurs dispositifs hétérogènes. Cette évolution favorise un nouveau modèle distribué de collaboration de confiance où les utilisateurs peuvent travailler sur des documents partagés avec qui ils ont confiance. La collaboration multi-synchrone est largement utilisée pour soutenir le travail collaboratif en maintenant des flux simultanés de l'activité des utilisateurs qui divergent et convergent continuellement. Cependant, ce modèle n'offre pas de support concernant l'expression et la vérification de restriction d'usage des données. Cette thèse présente C-PPC, un modèle de collaboration basé sur les contrats et sur la confiance. Dans ce modèle, des contrats sont utilisés comme des règles d'utilisation des données et les utilisateurs collaborent en fonction des niveaux de confiance qu'ils attribuent aux autres en accord avec le respect des contrats. Nous formalisons les contrats en utilisant des concepts déontiques: permission, obligation et prohibition. Les contrats sont inclus dans les historiques d'opérations des données partagées. Le modèle C-PPC fournit un mécanisme pour la fusion des modifications des données et des contrats. N'importe quel utilisateur peut auditer les historiques à n'importe quel moment et les résultats de l'audit sont utilisés pour actualiser les niveaux de confiance en se basant sur une métrique de confiance. Nous proposons une solution reposant sur des authentificateurs basés sur les chaînes de hachage pour garantir l'intégrité des historiques et la responsabilité des utilisateurs. Nous fournissons des algorithmes pour construire les authentificateurs et vérifier les historiques puis nous prouvons leur correction. Des résultats expérimentaux montrent la faisabilité du modèle C-PPC / Nowadays, information technologies provide users ability to work with anyone, at any time, from everywhere and with several heterogeneous devices. This evolution fosters a new distributed trustworthy collaboration model where users can work on shared documents with whom they trust. Multi-synchronous collaboration is widely used for supporting collaborative work by maintaining simultaneous streams of user activities which continually diverge and converge. However, this model lacks support on how usage restrictions on data can be expressed and checked within the model. This thesis proposes "C-PPC", a multi-synchronous contract-based and trust-aware collaboration model. In this model, contracts are used as usage rules and users collaborate according to trust levels they have on others computed according to contract compliance. We formalize contracts by using deontic concepts: permission, obligation and prohibition. Contracts are enclosed in logs of operations over shared data. The C-PPC model provides a mechanism for merging data changes and contracts. Any user can audit logs at any time and auditing results are used to update user trust levels based on a trust metric. We propose a solution relying on hash-chain based authenticators that ensures integrity of logs and user accountability. We provide algorithms for constructing authenticators and verifying logs and prove their correctness. A set of experimental results shows the feasibility of the C-PPC model

L’évolution technologique du web durant ces dernières années a favorisé l’arrivée d’environnements virtuels collaboratifs pour la modélisation 3D à grande échelle. Alors que la collaboration réunit dans un même espace partagé des utilisateurs distants géographiquement pour un objectif de collaboration commun, les ressources matérielles qu'ils apportent (calcul, stockage, 3D ...) avec leurs connaissances sont encore trop rarement utilisées et cela constitue un défi. Il s'agit en effet de proposer un système simple, performant et transparent pour les utilisateurs afin de permettre une collaboration efficace à la fois sur le volet computationnel mais aussi, bien entendu, sur l'aspect métier lié à la modélisation 3D sur le web. Pour rendre efficace le passage à l’échelle, de nombreux systèmes utilisent une architecture réseau dite "hybride", combinant client serveur et pair-à-pair. La réplication optimiste s'adapte bien aux propriétés de ces environnements répartis : la dynamicité des utilisateurs et leur nombre, le type de donnée traitées (3D) et leur taille. Cette thèse présente un modèle pour les systèmes d’édition collaborative en 3D sur le web. L'architecture cliente (3DEvent) permet de déporter les aspects métiers de la 3D au plus près de l’utilisateur sous la forme d’évènements. Cette architecture orientée événements repose sur le constat d’un fort besoin de traçabilité et d’historique sur les données 3D lors de l’assemblage d’un modèle. Cet aspect est porté intrinsèquement par le patron de conception event-sourcing. Ce modèle est complété par la définition d’un intergiciel en pair-à-pair. Sur ce dernier point, nous proposons d'utiliser la technologie WebRTC qui présente une API familière aux développeurs de services en infonuagique. Une évaluation portant sur deux études utilisateur concernant l’acceptance du modèle proposé a été menée dans le cadre de tâches d’assemblage de modèles 3D sur plusieurs groupes d’utilisateurs. / Web technologies evolutions during last decades fostered the development of collaborative virtual environments for 3D design at large scale. Despite the fact that collaborative environments gather in a same shared space geographically distant users in a common objective, the hardware ressources of their clients (calcul, storage, graphics ...) are often underused because of the challenge it represents. It is indeed a matter of offering an easy-to-use, efficient and transparent collaborative system to the user supporting both computationnal and 3D design visualisation and business logic needs in heterogeneous web environments. To scale well, numerous systems use a network architecture called "hybrid", combining both client-server and peer-to-peer. Optimistic replication is well adapted to distributed application such as 3D collaborative envionments : the dynamicity of users and their numbers, the 3D data type used and the large amount and size of it.This document presents a model for 3D web-based collaborative editing systems. This model integrates 3DEvent, an client-based architecture allowing us to bring 3D business logic closer to the user using events. Indeed, the need of traceability and history awareness is required during 3D design especially when several experts are involved during the process. This aspect is intrinsec to event-sourcing design pattern. This architecture is completed by a peer-to-peer middleware responsible for the synchronisation and the consistency of the system. To implement it, we propose to use the recent web standard API called WebRTC, close to cloud development services know by developers. To evaluate the model, two user studies were conducted on several group of users concerning its responsiveness and the acceptance by users in the frame of cooperative assembly tasks of 3D models.

De nombreuses catastrophes de diverses envergures frappent régulièrement des populations partout dans le monde. Parmi les exemples marquant on peut citer l'ouragan Katrina en 2005, le tremblement de terre en Haïti en 2010 ou plus récemment le Tsunami au Japon et la catastrophe de Fukujima qui a suivie. Au cours de ces catastrophes, plusieurs centaines d'organisations, comme la police, les pompiers ou les organisations d'aide humanitaire, interviennent pour sauver les gens et aider à revenir à une vie normale. Ces organisations ont besoin de se coordonner pour faire face à une situation dynamique avec des ressources limitées et une vision partielle de la situation. L'évolution de la situation entraîne souvent des changements d'objectif et de plan. Un des problèmes typique est d'obtenir un aperçu sur les relations entre ce qui a été fait, ce qui se passe actuellement et quelles sont les prochaines étapes. Ce problème est particulièrement difficile sur le plan inter-organisationnel : Chaque organisation coordonne la réponse de sa propre perspective et s'appuie sur les informations fournies par d'autres organisations. Notre objectif dans cette thèse est d'étudier comment supporter la coordination des activités par des personnes de différentes organisations dans une situation dynamique par un système d'information. L'idée de base est de tirer profit d'une approche basée sur les processus, où les activités et leurs relations sont rendues explicites. Nous présentons un cadre pour la coordination des activités dans des situations dynamiques. Il permet la modélisation ad hoc des relations entre ce qui a été fait, ce qui se passe actuellement et quelles sont les prochaines étapes. Les écarts par rapport au modèle et comment les activités ont été réalisées sont affichées à l'utilisateur pour mettre en évidence l'impact de l'évolution des objectifs. Nous étendons ce cadre au niveau inter-organisationnel. Certaines activités peuvent être partagées entre différentes organisations. Tout n'est pas partagé entre tout le monde pour tenir compte du respect de la vie privée, de la réglementation, des raisons stratégiques ou autres. Les activités partagées sont reproduites dans les espaces de travail de ces organisations. Nous décrivons comment des vues divergentes sur les activités et leurs relations peuvent etre détectées et traitées afin de revenir éventuellement à une vue convergente. Les concepts sont mis en œuvre comme une extension d'un service de collaboration distribuée ouvert. Ils ont été évalués par des gestionnaires de catastrophes expérimentés. Par ailleurs, nous avons conçu une expérience visant à évaluer l'utilisation d'outils pour aborder ces question. Nous avons effectué plusieurs expériences pour valider cette expérience. D'autres expériences pourront fournir une validation plus complété du modèle proposé dans cette thèse.

A discrete event system is a system whose state space is given by a discrete set and whose state transition mechanism is event-driven i.e. its state evolution depends only on the occurrence of discrete events over the time. These systems are used in many fields of application (telecommunication networks, aeronautics, aerospace,). The validity of these systems is then an important issue and to ensure it we can use supervisory control methods. These methods consist in imposing a given specification on a system by means of a controller which runs in parallel with the original system and which restricts its behavior. In this thesis, we develop supervisory control methods where the system can have an infinite state space and the controller has a partial observation of the system (this implies that the controller must define its control policy from an imperfect knowledge of the system). Unfortunately, this problem is generally undecidable. To overcome this negative result, we use abstract interpretation techniques which ensure the termination of our algorithms by overapproximating, however, some computations. The aim of this thesis is to provide the most complete contribution it is possible to bring to this topic. Hence, we consider more and more realistic problems. More precisely, we start our work by considering a centralized framework (i.e. the system is controlled by a single controller) and by synthesizing memoryless controllers (i.e. controllers that define their control policy from the current observation received from the system). Next, to obtain better solutions, we consider the synthesis of controllers that record a part or the whole of the execution of the system and use this information to define the control policy. Unfortunately, these methods cannot be used to control an interesting class of systems: the distributed systems. We have then defined methods that allow to control distributed systems with synchronous communications (decentralized and modular methods) and with asynchronous communications (distributed method). Moreover, we have implemented some of our algorithms to experimentally evaluate the quality of the synthesized controllers. / <p><p>Un système à événements discrets est un système dont l'espace d'états est un ensemble discret et dont l'évolution de l'état courant dépend de l'occurrence d'événements discrets à travers le temps. Ces systèmes sont présents dans de nombreux domaines critiques tels les réseaux de communications, l'aéronautique, l'aérospatiale. La validité de ces systèmes est dès lors une question importante et une manière de l'assurer est d'utiliser des méthodes de contrôle supervisé. Ces méthodes associent au système un dispositif, appelé contrôleur, qui s'exécute en parrallèle et qui restreint le comportement du système de manière à empêcher qu'un comportement erroné ne se produise. Dans cette thèse, on s'intéresse au développement de méthodes de contrôle supervisé où le système peut avoir un espace d'états infini et où les contrôleurs ne sont pas toujours capables d'observer parfaitement le système; ce qui implique qu'ils doivent définir leur politique de contrôle à partir d'une connaissance imparfaite du système. Malheureusement, ce problème est généralement indécidable. Pour surmonter cette difficulté, nous utilisons alors des techniques d'interprétation abstraite qui assurent la terminaison de nos algorithmes au prix de certaines sur-approximations dans les calculs. Le but de notre thèse est de fournir la contribution la plus complète possible dans ce domaine et nous considèrons pour cela des problèmes de plus en plus réalistes. Plus précisement, nous avons commencé notre travail en définissant une méthode centralisée où le système est contrôlé par un seul contrôleur qui définit sa politique de contrôle à partir de la dernière information reçue du système. Ensuite, pour obtenir de meilleures solutions, nous avons défini des contrôleurs qui retiennent une partie ou la totalité de l'exécution du système et qui définissent leur politique de contrôle à partir de cette information. Malheureusement, ces méthodes ne peuvent pas être utilisées pour contrôler une classe intéressante de systèmes: les sytèmes distribués. Nous avons alors défini des méthodes permettant de contrôler des systèmes distribués dont les communications sont synchrones (méthodes décentralisées et modulaires) et asynchrones (méthodes distribuées). De plus, nous avons implémenté certains de nos algorithmes pour évaluer expérimentalement la qualité des contrôleurs qu'ils synthétisent. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished