Academic literature on the topic 'Algorithmique Distribué'

Les problèmes d'optimisation des réseaux font partie des grandes axes de la recherche en télécommunications. On distingue les problèmes de dimensionnement, de routage, de reroutage, et de planification de la réserve. Notre travail de thèse, qui se situe dans le cadre d'une collaboration du cnet avec l'utc, a porté sur des études pour le reroutage. Son objectif de base était le développement d'outils performants pour la reconfiguration des réseaux en temps-réel dans le cas de grosses pannes dans un réseau de transmission. De telles pannes peuvent considérablement pénaliser la qualité de service (qs), si une reconfiguration rapide du réseau n'est pas engagée. Tout au long de cette thèse nous avons considère le cas du reroutage distribue pour les réseaux de transmission, nous avons propose deux nouveaux algorithmes de reroutage distribués. Le premier algorithme développé, est base sur l'utilisation de chemins prédéterminés. Ceci donne une méthode de reroutage hybride. En effet, son aspect precalculé réside dans la façon dont les chemins de restauration sont trouves, et son aspect distribue se concrétise dans le déroulement dynamique du reroutage. Conçu sur une toute autre idée, le deuxième algorithme utilise des chemins de restauration calcules en temps-réel. Le nœud responsable du reroutage calcule les chemins candidats en se basant sur sa propre vision du réseau. Remarquons que la vision des nœuds sur le réseau évolue en fonction des informations apportées par les messages, ce qui permet un calcul fiable des chemins de restauration. L'étude théorique de ces algorithmes a été suivie d'un travail informatique important. Nous présentons les résultats obtenus par la simulation (en c) de nos algorithmes de reroutage et les comparons avec ceux obtenus par les algorithmes de la littérature, ce qui démontre la supériorité de nos algorithmes. Enfin, nous avons considéré le problème du sur-dimensionnement des réseaux sdh, qui se pose généralement comme un plne. Nous avons conçu et développé une approche qui utilise les résultats du problème relaxe (pl) pour obtenir une solution en nombres entiers proche de l'optimum.

Cette étude concerne la distribution d'applications sur des machines de type réseau d’ordinateurs ou grappe de processeurs. Ce type de machine est observé de manière théorique puis de manière pratique, à travers différentes mesures. Le contexte des applications irrégulières est privilégié, leur distribution posant encore souvent des problèmes d'efficacité. La distribution des applications régulières est abordée plus succinctement. Une démarche de développement d’application distribuée ainsi que des outils de programmation sont proposés. Ll est notamment proposé d’utiliser la paresse comme outils de distribution des données ainsi que d'effectuer un découpage récursif et dynamique des calculs au fur et a mesures des assignations de tâches. Ces propositions sont ensuite validées par l’étude d’un cas concret, le lancer de rayon distribué. Enfin l'applicabilité des ces propositions à des cas plus généraux est étudiée et des critères sont dégagés, permettant d’évaluer l'opportunité d'utiliser ces outils originaux en fonction des caractéristiques de l'application à distribuer.

Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performances
Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances

Les systèmes dynamiques continus permettent de modéliser de nombreux
systèmes physiques, biologiques, ou issus de l'informatique
distribuée. Nous nous intéressons à leur pouvoir de modélisation, et à
leurs propriétés en tant que systèmes de calculs, et plus généralement
aux propriétés calculatoires des modèles continus.

Les deux premiers chapitres ne visent pas à produire des résultats
nouveaux, mais à motiver ce travail, et à le mettre en
perspectives. Le chapitre 3 constitue un survol. Les chapitres 4, 5 et
l'annexe A présentent un panorama de quelques-uns de nos résultats
personnels en relations avec cette problématique.

Plus précisément, le chapitre 1 présente les systèmes dynamiques, avec
un point de vue classique et mathématique. Il vise d'une part à
souligner la richesse, et la subtilité des comportements possibles des
systèmes dynamiques continus, et d'autre part à mettre en évidence que
différents dispositifs sont intrinsèquement continus, et utilisables
comme tels pour réaliser des calculs. En outre nous insistons sur la
puissance de modélisation d'une classe de systèmes dynamiques, que
nous nommons les problèmes de Cauchy polynomiaux.

Les exemples du chapitre 2, issus de la bioinformatique, des modèles
de la biologie des populations, de la virologie biologique et de la
virologie informatique, et de l'algorithmique distribuée, se
distinguent de ceux du chapitre 1 par le fait qu'ils mettent
explicitement en jeu une certaine notion de concurrence entre agents.
Nous présentons la théorie des jeux, et ses modèles, en nous
focalisant sur certains de ses modèles du dynamisme. Ces modèles
continus deviennent naturels pour parler d'algorithmique distribuée,
en particulier dès que l'on a affaire à des systèmes de grandes
tailles, ou dont on ne contrôle pas les interactions. Nous pointons
quelques modèles de l'algorithmique distribuée qui intègrent ces
considérations, et le potentiel de l'utilisation des systèmes continus
pour l'algorithmique distribuée.

Le chapitre 3 constitue un survol de la théorie des calculs pour les
modèles à temps continu. La puissance des modèles de calculs à temps
et espace discrets est relativement bien comprise grâce à la thèse de
Church, qui postule que tous les modèles raisonnables et suffisamment
puissants ont la même puissance, celle des machines de Turing. On peut
aussi considérer des modèles où le temps est continu. Certaines
grandes classes de modèles ont été considérées dans la
littérature. Nous les reprenons dans ce chapitre, en présentant un
panorama de ce qui est connu sur leurs propriétés calculatoires.

Le chapitre 4 présente un résumé de quelques-uns de nos résultats
personnels à propos de la comparaison de la puissance de plusieurs
modèles à temps continu, en relations avec la thèse de Emmanuel
Hainry. Claude Shannon a introduit en 1941 le GPAC comme un modèle des
dispositifs de calculs analogiques. Les résultats de Shannon ont
longtemps été utilisés pour argumenter que ce modèle était plus faible
que l'analyse récursive, et donc que les machines analogiques sont
prouvablement plus faibles que les machines digitales. Avec Manuel
Campagnolo, Daniel Graça, et Emmanuel Hainry, nous avons prouvé
récemment que le GPAC et l'analyse récursive calculent en fait les
mêmes fonctions. Ce résultat prend toute sa perspective si l'on
comprend que les fonctions calculées par le GPAC correspondent aux
problèmes de Cauchy polynomiaux, dont le pouvoir de modélisation est
discuté dans le chapitre 1.

D'autre part, nous avons montré qu'il était possible de caractériser
algébriquement les fonctions élémentairement calculables et
calculables au sens de l'analyse récursive. Cela signifie d'une part
qu'il est possible de les caractériser en termes d'une sous-classe des
fonctions R-récursives à la Moore, ce qui étend les résultats de
Campagnolo, Costa, Moore, de la calculabilité discrète à l'analyse
récursive, mais aussi d'autre part, qu'il est possible de caractériser
ces fonctions de façon purement continue, par l'analyse, sans
référence à de la calculabilité.

Dans le chapitre 5, nous reprenons certains de nos résultats à propos
de caractérisations logiques de classes de complexité dans le modèle
de Blum Shub et Smale, en relations avec la thèse de Paulin Jacobé de
Naurois. Le modèle de Blum Shub et Smale constitue un modèle de calcul
à temps discret et à espace continu. Le modèle, défini initialement
pour parler de complexité algébrique de problèmes sur le corps des
réels, ou plus généralement sur un anneau, a été par la suite été
étendu par Poizat en un modèle de calculs sur une structure logique
arbitraire. Avec Paulin Jacobé de Naurois, Felipe Cucker et Jean-Yves
Marion, nous avons caractérisé syntaxiquement les classes de
complexité majeures dans ce modèle sur une structure arbitraire, à la
Bellantoni et Cook 1992.

Le chapitre 6 est consacré à une conclusion, dans laquelle nous
reprenons plusieurs questions et perspectives qui nous semblent
intéressantes.

Dans l'annexe A, nous discutons un point de vue sur les
hypercalculs. La question de l'existence de systèmes capables de
réaliser des hypercalculs, c'est-à-dire d'effectuer des calculs
exploitables qui ne seraient pas réalisables par aucune machine de
Turing, fait encore couler de l'encre et des controverses. Nous avons
été invité à exprimer notre point de vue dans un numéro spécial sur le
sujet, que nous reprenons en annexe A. Nous y rappelons plusieurs
mauvaises compréhensions fréquentes de la thèse de Church, et nous
présentons un panorama de plusieurs classes de systèmes mathématiques,
avec la caractérisation de leur puissance.

Cette thèse présente un modèle de traitement parallèle pour la mise en œuvre d'algorithmes de raisonnement dans le cadre d'un système temps-réel intelligent, et s'inscrit dans l'étude SATURNE menée au CERT-ONERA. Ce projet se fonde sur l'hypothèse que les tâches de traitement ont la capacité de s'adapter aux échéances temporelles. Pour satisfaire ce modèle, les solutions proposées sont la réduction de l'espace de recherche et l'accélération des traitements grâce au parallélisme. Ces changements devant intervenir durant l'exécution du processus, la gestion du parallélisme devient alors dynamique. Par ailleurs, les arbres de décision représentent une méthode fondamentale pour résoudre de nombreux problèmes d'intelligence artificielle, tels que la théorie des jeux à un joueur, les problèmes d'optimisation, la théorie des jeux à deux joueurs, les graphes Et/Ou et beaucoup d'autres problèmes NP-complets. Aussi, à partir de l'exemple de l'algorithme du minimax sur des arbres de jeux réels, une implémentation est réalisée sur Modulor, une machine à architecture distribuée à base de transputers développée au CERT-ONERA. La méthode de parallélisation se fonde sur une suppression du contrôle entre les processus de recherche, au profit d'un parallélisme spéculatif et du partage complet de l'information réalisé grâce à une mémoire physiquement distribuée mais virtuellement partagée. L’apport de notre approche pour les systèmes temps-réel distribués et tolérants aux fautes est évalué grâce aux résultats expérimentaux obtenus.

Un système distribué peut être représenté par un graphe étiqueté : les sommets correspondent aux processeurs, les arêtes aux liens de communication et les étiquettes associées aux sommets codent les états des processeurs. Un algorithme distribué est alors décrit par un système de règles de transition locale où l'étiquette suivante d'un sommet est fonction de son étiquette actuelle et de celles de ses voisins (réétiquetage local). Les réétiquetages opérant sur des voisinages disjoints se déroulent en parallèle, de manière asynchrone. Dans ce cadre, on étudie la réalisabilité et non-réalisabilité des tâches distribuées. Nous illustrerons notre méthode en nous intéressant en particulier à certains problèmes spécifiques aux systèmes distribués (élection d'un noeud, reconnaissance de certaines propriétés topologiques du graphe sous-jacent au réseau, calcul de métriques du réseau comme par exemple la taille ou le diamètre). Dans tous ces cas, on présente une caractérisation complète de ce qui est réalisable par calcul distribué en fonction de la topologie du graphe sous-jacent mais également du degré de connaissance qu'a le réseau sur lui-même ("connaissance structurelle"). Ces conditions nécessaires et suffisantes sont principalement exprimées en termes de fermetures par s̀̀imilarités'' des familles de réseaux considérées. Ces s̀̀imilarités'' sont décrites de manière combinatoire à l'aide de morphismes de graphes particuliers : les revêtements et les quasi-revêtements. Les preuves des conditions nécessaires emploient des techniques de simulation à base de revêtements et quasi-revêtements. Les algorithmes distribués présentés pour les preuves des conditions suffisantes se fondent essentiellement sur un algorithme de cartographie du réseau sous-jacent. Celui-ci est construit à partir des extensions d'un algorithme d'énumération de A. Mazurkiewicz et d'un algorithme de détection des propriétés stables de Shy, Szymanski et Prywes.

Les réseaux de capteurs mobiles font leur apparition en informatique depuis plusieurs années. Certaines caractéristiques de ces réseaux sont nouvelles : les capteurs sont petits, avec peu de mémoire, peuvent tomber en panne facilement, sont mobiles. De plus, ces réseaux contiennent parfois plusieurs milliers d'entités. L'enjeu pour l'informatique est de taille. En effet, ces nouvelles propriétés posent un défi pour les concepteurs d'algorithmes que nous sommes. Il est nécessaire de repenser nos méthodes et d'assurer algorithmiquement que ces nouveaux systèmes fonctionneront correctement dans le futur. La difficulté théorique et l’enjeu de ces problèmes en font un sujet de recherche à la fois intéressant et excitant. Le but de cette thèse est de reconsidérer certains algorithmes conçus pour des réseaux classiques afin qu'ils soient performants sur des réseaux émergents. Nous ne nous sommes pas uniquement focalisé sur les réseaux de capteurs mobiles mais aussi sur d'autres systèmes ayant vu le jour ces dernières années. Enfin, nous avons tenté systématiquement d'introduire des probabilités afin de débloquer des impossibilités ou même d'améliorer les performances des algorithmes. Nous avons obtenu différents résultats, sur plusieurs types de réseaux émergents tels que les réseaux pair à pair, les réseaux de robots ou les réseaux de capteurs mobiles pour lesquels nous étendons le modèle des protocoles de population. Enfin, nous proposons un modèle formel permettant de mesurer l’étendue des connexions entre les différents types de réseaux, ou tout du moins entre les modèles les décrivant
Mobile sensor networks have appeared in computer science several years ago. Some of these networks’ characteristics are new: sensors are small, with few memory; they can be corrupted easily and are mobile. Moreover, they may contain thousands of entities. For computer science, the stake is huge. All these new properties are a challenge for us, algorithm creators. It is necessary to adapt our methods and to make sure that from an algorithmic point of view, these new systems will function correctly in the years to come. The theoretical difficulty and the stake of these issues transform them into an interesting and exciting research subject. The goal this thesis is to reconsider some of the algorithms created for classical networks in order to make them performing on these new networks. We did not restrain ourselves to mobile sensor networks and also considered other recent systems. Also, we always introduced probability in order to unblock impossibilities or to improve the performance of the algorithms. We obtained different results on several kinds of new networks as peer to peer networks, robots networks or mobile sensor networks in which we extend the population protocol model. Finally, we introduced a formal model in order to prove that at some level of abstraction, there are very strong connections between the various types of networks, or at least between the models describing them

Présentation d'un cadre général pour l'étude et l'analyse des algorithmes répartis et résolution de plusieurs problèmes de fond relatifs à la complexité dans les systèmes répartis. Développement de divers outils d'analyse en moyenne de la complexite en messages de protocoles généraux à consensus. Résolution par l'analyse mathématique d'un problème ouvert sur les performances comparées des anneaux uni et bidirectionnels pour la complexité en moyenne en messages d'algorithmes d'élection déterministes. Un algorithme probabiliste de construction d'un arbre couvrant sur un système distribué anonyme et quelconque est développé. Deux théorèmes sont proposés qui bornent la faille des messages en fonction de la complexite en messages des algorithmes distribués asynchrones du point de vue de la quantité d'information.

En algorithmique distribuée, le modèle asynchrone par envoi de messages et à pannes est connu et utilisé dans de nombreux articles de par son réalisme,par ailleurs il est suffisamment simple pour être utilisé et suffisamment complexe pour représenter des problèmes réels. Dans ce modèle, les n processus communiquent en s'échangeant des messages, mais sans borne sur les délais de communication, c'est-à-dire qu'un message peut mettre un temps arbitrairement long à atteindre sa destination. De plus, jusqu'à f processus peuvent tomber en panne, et ainsi arrêter définitivement de fonctionner. Ces pannes indétectables à cause de l'asynchronisme du système limitent les possibilités de ce modèle. Dans de nombreux cas, les résultats connus dans ces systèmes sont limités à une stricte minorité de pannes. C'est par exemple le cas de l'implémentation de registres atomiques et de la résolution du renommage. Cette barrière de la majorité de pannes, expliquée par le théorème CAP, s'applique à de nombreux problèmes, et fait que le modèle asynchrone par envoi de messages avec une majorité de pannes est peu étudié. Il est donc intéressant d'étudier ce qu'il est possible de faire dans ce cadre.Cette thèse cherche donc à mieux comprendre ce modèle à majorité de pannes, au travers de deux principaux problèmes. Dans un premier temps, on étudie l'implémentation d'objets partagés similaires aux registres habituels, en définissant les bancs de registres x-colorés et les α-registres. Dans un second temps, le problème du renommage est étendu en renommage k-redondant, dans ses versions à-un-coup et réutilisable, et de même pour les objets partagés diviseurs, étendus en k-diviseurs
In distributed computing, asynchronous message-passing model with crashes is well-known and considered in many articles, because of its realism and it issimple enough to be used and complex enough to represent many real problems.In this model, n processes communicate by exchanging messages, but withoutany bound on communication delays, i.e. a message may take an arbitrarilylong time to reach its destination. Moreover, up to f among the n processesmay crash, and thus definitely stop working. Those crashes are undetectablebecause of the system asynchronism, and restrict the potential results in thismodel.In many cases, known results in those systems must verify the propertyof a strict minority of crashes. For example, this applies to implementationof atomic registers and solving of renaming. This barrier of a majority ofcrashes, explained by the CAP theorem, restricts numerous problems, and theasynchronous message-passing model with a majority of crashes is thus notwell-studied and rather unknown. Hence, studying what can be done in thiscase of a majority of crashes is interesting.This thesis tries to analyse this model, through two main problems. The first part studies the implementation of shared objects, similar to usual registers,by defining x-colored register banks, and α-registers. The second partextends the renaming problem into k-redundant renaming, for both one-shotand long-lived versions, and similarly for the shared objects called splitters intok-splitters