A distributed approach to covering problems in highly dynamic systems
Une approche distribuée pour les problèmes de couverture dans les systèmes hautement dynamiques
Résumé
A distributed system is a system composed of autonomous computing units enhanced with communication capacities. It is a common model for algorithmic study of networks. The quick evolution of mobiles/wireless networks leads to include the dynamics (i.e. the ability of the connectivity to evolve with time) in distributed computing. In other words, this means that we add the assumption that the communication capacities of system units may evolve with time.
Numerous model of distributed systems consider the dynamics as an independent characteristic of the system (and not as a communication fault). A new model, called time varying graph, try to unify all these models in a common formalism that allow to classify these systems in function of their properties of temporal connectivity. In this thesis, we interest in highly dynamic distributed systems in which the connectivity assumptions are minimalist. More precisely, we focus on connected over time systems in which the only guarantee is that every unit can infinitely often send a message to every other unit of the system (without any guarantees on the life time of the route nor on the communication delay). We specifically target covering problems (like minimal dominating set, maximal matching, maximal independent set, ...) in these highly dynamic distributed systems.
Contributions of this thesis in this context are the following. First, we propose a new definition of covering problems that is more suitable to highly dynamic distributed systems than existing ones. Then, we provide a generic tool to simplify impossibility result proofs in dynamic distributed systems. We apply this tool to prove several impossibility results related to covering problems. We also propose a new time complexity measure that allow to fairly compare protocol performances in dynamic distributed systems. Finally, we give a minimal dominating set construction algorithm in highly dynamic distributed systems.
Un système distribué est un système composé d'éléments de calcul autonomes dotés de capacité de communication. Il s'agit d'un modèle commun pour l'étude des réseaux. L'évolution rapide des réseaux sans fils et/ou mobiles aussi bien dans la vie quotidienne que dans la recherche amène progressivement à intégrer la dynamique (i.e. l'évolution dans le temps de la connectivité) dans les systèmes distribués. Concrètement, cela revient à ajouter l'hypothèse que les capacités de communication des éléments du système peuvent varier dans le temps.
De nombreux modèles considèrent ainsi la dynamique comme composante à part entière du système (et non pas comme une faute). De manière récente, une nouvelle approche, appelée graphe variant dans le temps, tente d'unifier tous ces modèles dans un formalisme commun qui permet de classifier les systèmes en fonction de leurs propriétés de connexité temporelle. Dans cette thèse, nous nous intéressons à des systèmes distribués hautement dynamiques dans lesquels les hypothèses de connexité sont minimalistes. Plus précisément, nous concentrons nos efforts sur les systèmes connexes à travers le temps dans lesquels la seule garantie est que tout élément du système peut infiniment souvent envoyer un message à tout autre (sans garantie sur la pérennité de la route utilisée ni sur le délai de communication). Nous nous intéressons plus particulièrement aux problèmes de couverture (par exemple, ensemble dominant minimal, couplage maximal, ensemble indépendant maximal, ...) dans ces systèmes distribués hautement dynamiques.
Les contributions de cette thèse dans ce contexte sont les suivantes. Nous proposons tout d'abord une nouvelle définition pour les problèmes de couverture qui est plus adaptée aux systèmes distribués hautement dynamiques que les définitions existantes. Dans un deuxième temps, nous fournissons un outil générique qui permet de faciliter les preuves de résultats d'impossibilité dans les systèmes distribués dynamiques. Nous appliquons cet outil pour prouver plusieurs résultats d'impossibilité à propos de problèmes de couverture. Ensuite, nous proposons une nouvelle mesure de complexité en temps qui permet de comparer équitablement les performances de protocoles dans les systèmes distribués dynamiques. Enfin, nous donnons un algorithme de construction d'un ensemble dominant minimal dans les systèmes distribués hautement dynamiques.
Loading...