Дисертації з теми "Algorithmique Distribué"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Algorithmique Distribué.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Algorithmique Distribué".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Nace, Dritan. "Contribution au réroutage distribué dans les réseaux de télécommunication." Compiègne, 1997. http://www.theses.fr/1997COMP997S.
Анотація:
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.
2
Poitou, Olivier. "Une algorithmique adaptée à la distribution pour la résolution de problèmes irréguliers." Toulouse, ENSAE, 2003. http://www.theses.fr/2003ESAE0008.
Анотація:
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.
3
Lefevre, Jonas. "Protocoles de population : une hiérarchie des variantes. Calcul de couplages autostabilisants." Palaiseau, Ecole polytechnique, 2014. http://www.theses.fr/2014EPXX0068.
4
Hinge, Antoine. "Dessin de graphe distribué par modèle de force : application au Big Data." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0092/document.
Анотація:
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 performancesGraphs, 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
5
Bournez, Olivier. "Modèles Continus. Calculs. Algorithmique Distribuée." Habilitation à diriger des recherches, Institut National Polytechnique de Lorraine - INPL, 2006. http://tel.archives-ouvertes.fr/tel-00123104.
Анотація:
Les systèmes dynamiques continus permettent de modéliser de nombreuxsystè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.
6
David, Vincent. "Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint : étude et application au minimax." Toulouse, ENSAE, 1993. http://www.theses.fr/1993ESAE0008.
Анотація:
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.
7
Godard, Emmanuel. "Réécritures de graphes et algorithmique distribuée." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12518.
Анотація:
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.
8
Clément, Julien. "Algorithmique probabiliste pour systèmes distribués émergents." Paris 11, 2009. http://www.theses.fr/2009PA112231.
Анотація:
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écrivantMobile 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
9
Lavault, Christian. "Algorithmique et complexité distribuées : applications à quelques problèmes fondamentaux de complexité, protocoles distribués à consensus, information globale, problèmes distribués d'élection et de routage." Paris 11, 1987. http://www.theses.fr/1987PA112392.
Анотація:
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.
10
Bonnin, David. "Algorithmique distribuée asynchrone avec une majorité de pannes." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0264/document.
Анотація:
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-diviseursIn 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
11
Chalopin, Jérémie. "Algorithmique distribuée, calculs locaux et homomorphismes de graphes." Bordeaux 1, 2006. http://www.theses.fr/2006BOR13257.
Анотація:
Dans cette thèse, on étudie ce qui est calculable dans différents modèles d'algorithmique distribuée. Les modèles considérés correspondent à différents niveaux d'abstraction et à différents niveaux de synchronisation entre les processus d'un système distribué. On s'intéresse en particulier au problèmes de l'élection et du nommage dans ces différents modèles. Pour chaque modèle, on caractérise les systèmes distribués dans lesquels on peut résoudre ces problèmes et on étudie la complexité des problèmes de décision correspondants. Nos caractérisations utilisent des homomorphismes de graphes qui préservent certaines propriétés locales. Nos preuves sont constructives : quand on peut résoudre l'élection (ou le nommage) dans un réseau, on présente un algorithme d'élection (ou de nommage) pour ce réseau. Ces problèmes permettent de mettre en évidence les différences entre les puissances de calculs des différents modèles considérés. De plus, l'étude de ces problèmes permet de mettre à jour les bons outils qui permettent d'étudier ce qui est calculable de manière distribuée dans les différents modèles.
12
Lejeune, Jonathan. "Algorithmique distribuée d'exclusion mutuelle : vers une gestion efficace des ressources." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066174/document.
Анотація:
Les systèmes à grande échelle comme les Grilles ou les Nuages (Clouds) mettent à disposition pour les utilisateurs des ressources informatiques hétérogènes. Dans les Nuages, les accès aux ressources sont orchestrés par des contrats permettant de définir un niveau de qualité de service (temps de réponse, disponibilité ...) que le fournisseur doit respecter. Ma thèse a donc contribué à concevoir de nouveaux algorithmes distribués de verrouillage de ressources dans les systèmes large échelle en prenant en compte des notions de qualité de service. Dans un premier temps, mes travaux de thèse se portent sur des algorithmes distribués de verrouillage ayant des contraintes en termes de priorités et de temps. Deux algorithmes d'exclusion mutuelle ont été proposés : un algorithme prenant en compte les priorités des clients et un autre pour des requêtes avec des dates d'échéance. Dans un second temps, j'ai abordé le problème de l'exclusion mutuelle généralisée pour allouer de manière exclusive plusieurs types de ressources hétérogènes. J'ai proposé un nouvel algorithme qui réduit les coûts de synchronisation en limitant la communication entre processus non conflictuels. Tous ces algorithmes ont été implémentés et évalués sur la plateforme nationale Grid 5000. Les évaluations ont montré que nos algorithmes satisfaisaient bien les contraintes applicatives tout en améliorant de manière significative les performances en termes de taux d'utilisation et de temps de réponseDistributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time
13
Lejeune, Jonathan. "Algorithmique distribuée d'exclusion mutuelle : vers une gestion efficace des ressources." Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066174.
Анотація:
Les systèmes à grande échelle comme les Grilles ou les Nuages (Clouds) mettent à disposition pour les utilisateurs des ressources informatiques hétérogènes. Dans les Nuages, les accès aux ressources sont orchestrés par des contrats permettant de définir un niveau de qualité de service (temps de réponse, disponibilité ...) que le fournisseur doit respecter. Ma thèse a donc contribué à concevoir de nouveaux algorithmes distribués de verrouillage de ressources dans les systèmes large échelle en prenant en compte des notions de qualité de service. Dans un premier temps, mes travaux de thèse se portent sur des algorithmes distribués de verrouillage ayant des contraintes en termes de priorités et de temps. Deux algorithmes d'exclusion mutuelle ont été proposés : un algorithme prenant en compte les priorités des clients et un autre pour des requêtes avec des dates d'échéance. Dans un second temps, j'ai abordé le problème de l'exclusion mutuelle généralisée pour allouer de manière exclusive plusieurs types de ressources hétérogènes. J'ai proposé un nouvel algorithme qui réduit les coûts de synchronisation en limitant la communication entre processus non conflictuels. Tous ces algorithmes ont été implémentés et évalués sur la plateforme nationale Grid 5000. Les évaluations ont montré que nos algorithmes satisfaisaient bien les contraintes applicatives tout en améliorant de manière significative les performances en termes de taux d'utilisation et de temps de réponseDistributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time
14
Maignan, Luidnel. "Points, distances, et automates cellulaires : algorithmique géométrique et spatiale." Paris 11, 2010. http://www.theses.fr/2010PA112325.
Анотація:
Le calcul spatial a pour but de fournir un cadre de travail passant à l'échelle où les calculs sont distribués sur un milieu de calculs uniforme à communications locales. Nous étudions le cas particulier des automates cellulaires, utilisant une grille régulière et une communication synchrone. Nous proposons de développer des primitives permettant de structurer le milieu de calculs autour d'un ensemble de particules. Nous considérons trois problèmes géométriques : déplacer les particules afin d'uniformiser leur densité, construire leur enveloppe convex, et construire un graphe de proximité connexe connectant les plus proches particules entre elles. Ces deux derniers problèmes sont considérés sur grille multidimensionnelle, tandis que l'uniformisation est résolue sur un espace à une dimension. Notre approche est de considérer l'espace métrique correspondant à l'automate cellulaire et de construire des objets mathématiques basés sur cette métrique seule. Les algorithmes obtenues se généralisent ainsi vers des grilles arbitraires. Nous implantons les grilles usuelles : hexagonale et carré avec 4 et 8 voisins. Toutes les solutions sont basées sur la même brique de base : le champ de distances, associant à chaque point de l'espace sa distance à la plus proche particule. Alors que ces valeurs de distances ne sont pas bornées, nous utilisons le fait que la différence entre valeurs voisines l'est afin d'encoder les gradients sur un nombre fini d'états. Nos algorithmes, exprimés en terme de mouvement par rapport à ces gradients et de détection de motifs de gradient, s'encodent donc en automates d'états finis, avec un petit nombre d'étatsSpatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a regular grid and synchronous update. We propose to develop primitives allowing to structure the medium around a set of particles. We consider three problems of geometrical nature: moving the particles on the grid in order to uniformize the density, constructing their convex hull, constructing a connected proximity graph establishing connection between nearest particles. The last two problems are considered for multidimensional grid while uniformization is solved specifically for the one dimensional grid. The work approach is to consider the metric space underlying the cellular automata topology and construct generic mathematical object based solely on this metric. As a result, the algorithms derived from the properties of those objects, generalize over arbitrary regular grid. We implemented the usual ones, including hexagonal, 4 neighbors, and 8 neighbors square grid. All the solutions are based on the same basic component: the distance field, which associates to each site of the space its distance to the nearest particle. While the distance values are not bounded, it is shown that the difference between the values of neighboring sites is bounded, enabling encoding of the gradient into a finite state field. Our algorithms are expressed in terms of movements according to such gradient, and also detecting patterns in the gradient, and can thus be encoded in finite state of automata, using only a dozen of state
15
Naz, André. "Algorithmique distribuée pour grands ensembles de robots : centralité, synchronisation et auto-reconfiguration." Thesis, Bourgogne Franche-Comté, 2017. http://www.theses.fr/2017UBFCD027/document.
Анотація:
Les récentes avancées technologiques en particulier dans le domaine de la miniaturisation de dispositifs robotiques laissent présager l'émergence de grands ensembles distribués de petits robots qui coopéreront en vue d'accomplir des tâches complexes (e.g., robotique modulaire, robots en essaims, microsystèmes électromécaniques distribués). Ces grands ensembles seront composés d'entités indépendantes, intelligentes et communicantes qui agiront comme un ensemble à part entière. Pour cela, elles s'auto-organiseront et collaboreront en vue d'accomplir des tâches complexes. Ces systèmes présenteront les avantages d'être plus polyvalents et plus robustes que les systèmes robotiques conventionnels tout en affichant un prix réduit. Ces ensembles formeront des systèmes distribués complexes dans lequel chaque entité sera un système embarqué à part entière avec ses propres capacités et ressources toute fois limitées. Coordonner de tels systèmes posent des défis majeurs et ouvrent de nouvelles opportunités dans l'algorithmique distribuée. Je défends la thèse qu'il faut d'ores et déjà identifier et implémenter des algorithmes distribués servant de primitives de base à la coordination de ces ensembles. Dans ce travail, nous nous focalisons sur une classe particulière de robots, à savoir les robots modulaires distribués formant de grands ensembles de modules fortement contraints en ressources (mémoire, calculs, etc.), placés dans une grille régulière et capables de communiquer entre voisins connexes uniquement. J'ai identifié et implémente trois primitives servant à la coordination de ces systèmes, à savoir l'élection d'un nœud central au réseau, la synchronisation temporelle ainsi que l'auto-reconfiguration. Dans ce manuscrit, je propose un ensemble d'algorithmes distribués réalisant ces primitives. J'ai évalué mes algorithmes en utilisant des expériences sur des modules matériels et en simulation sur des systèmes, composés de quelques dizaines à plus d'une dizaine de milliers de modules. Ces expériences montrent que nos algorithmes passent à l'échelle et sont adaptés aux grands ensembles distribués de systèmes embarqués avec des ressources fortement limités à la fois en mémoire et en calculTechnological advances especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex tasks (e.g., modular self-reconfigurable robots, swarm robotic systems, distributed microelectromechanical systems, etc.). These ensembles are formed from independent, intelligent and communicating units which act as a whole ensemble. These units cooperatively self-organize themselves to achieve common goals. These systems are tought to be more versatile and more robust than conventional robotic systems while having at the same time a lower cost.These ensembles form complex asynchronous distributed systems in which every unit is an embedded system with its own but limited capabilities. Coordination of such large-scale distributed embedded systems poses significant algorithmic issues and open for new opportunities in distributed algorithms. In my thesis, I defend the idea that distributed algorithmic primitives suitable for the coordination of these ensembles should be both identified and designed.In this work, we focus on a specific class of modular robotics systems, namely large-scale distributed modular robotic ensembles composed of resource-constrained modules that are organized in a lattice structure and which can only communicate with neighboring modules. We identified and implemented three building blocks, namely centrality-based leader election, time synchronization and self-reconfiguration.We propose a collection of distributed algorithms to realize these primitives. We evaluate them using both hardware experiments and simulations on systems ranging from a dozen of modules to more than a dozen of thousands of modules. We show that our algorithms scale well and are suitable for large-scale embedded distributed systems with scarce memory and computing resources
16
Tourancheau, Bernard. "Algorithmique parallèle pour les machines à mémoire distribuée : application aux algorithmes matriciels." Grenoble INPG, 1989. http://tel.archives-ouvertes.fr/tel-00332663/.
Анотація:
Différents résultats de complexité sont présentés pour les communications et le calcul sur des machines à mémoire distribuée. Les topologies concernées sont le réseau linéaire, l'anneau, la grille, l'hypercube et le réseau complet. Un réseau systolique est présenté pour l'algorithme de diagonalisation de Jordan. Une étude sur l'accélération et une étude de l'allocation des données sont formulées dans le contexte des mémoires distribuées
17
Farhat, Ayman. "Techniques algorithmiques pour la fiabilité et la sûreté des systèmes distribués." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape10/PQDD_0004/MQ40581.pdf.
18
Pérez, Garcia Julio César. "Contribution to security and privacy in the Blockchain-based Internet of Things : Robustness, Reliability, and Scalability." Electronic Thesis or Diss., Avignon, 2023. http://www.theses.fr/2023AVIG0120.
Анотація:
L’Internet des Objets (IoT, Internet of Things) est un réseau diversifié d’objets interconnectés, généralement via l’internet. En raison de la sensibilité des informations échangées dans les applications de IoT, il est essentiel de garantir la sécurité et le respect de la vie privée. Ce problème est aggravé par la nature ouverte des communications sans fil et par les contraintes de puissance et de ressources computationnelles de la plupart des appareils IoT. Parallèlement, les solutions de sécurité IoT existantes sont basées sur des architectures centralisées, ce qui pose des problèmes d’évolutivité et de point de défaillance unique, les rendant sensibles aux attaques par déni de service et aux défaillances techniques. La Blockchain est considérée comme une solution attractive aux problèmes de sécurité et de centralisation de IoT. Les Blockchains reproduisent un enregistrement permanent, en annexe seulement, de toutes les transactions effectuées sur un réseau entre plusieurs appareils, en les maintenant synchronisées par un protocole de consensus. L’utilisation de la Blockchain peut impliquer des coûts de calcul et d’énergie élevés pour les appareils. Par conséquent, des solutions basées sur Fog/Edge Computing ont été envisagées dans le cadre de l’intégration avec l’IoT. Cette approche transfère la charge de calcul et la consommation d’énergie plus élevées vers les dispositifs ayant une plus grande disponibilité de ressources, les dispositifs Fog/Edge. Toutefois, le coût de l’utilisation de la Blockchain doit être optimisé, en particulier dans le protocole de consensus, qui influe considérablement sur les performances globales du système. Les Blockchains avec permission correspondent mieux aux exigences des applications IoT que les Blockchains sans permission, en raison de leur taux élevé de traitement des transactions et de leur scalabilité. En effet, les nœuds de consensus, les validateurs, sont connus et prédéterminés. Dans les protocoles de consensus existants utilisés dans les Blockchains avec permission, les validateurs sont généralement un ensemble de nœuds prédéfinis ou sélectionnés de manière aléatoire, ce qui affecte à la fois les performances du système et l’équité (Fairness) entre les utilisateurs. L’objectif de ce travail est de proposer des solutions pour améliorer la sécurité et la vie privée dans IoT en intégrant la technologie Blockchain, ainsi que pour maximiser les niveaux de fairness pendant le consensus. L’étude est organisée en deux parties distinctes : l’une traite des aspects critiques de la sécurité de IoT et propose des solutions basées sur la Blockchain, tandis que l’autre se concentre sur l’optimisation de la Fairness entre les utilisateurs lors de l’exécution de l’algorithme de consensus sur la Blockchain. Nous présentons un mécanisme d’authentification inspiré du protocole d’authentification µTesla, qui utilise des clés symétriques formant une chaîne de hachage et obtient des propriétés asymétriques en dévoilant la clé utilisée un peu plus tard. Grâce à ce mécanisme et à l’utilisation de la Blockchain pour stocker les clés et faciliter l’authentification, notre proposition garantit une authentification robuste et efficace des appareils, sans qu’il soit nécessaire de recourir à un tiers de confiance. En outre, nous présentons un système de gestion des clés basé sur la Blockchain pour les communications de groupe, adapté aux contextes de IoT. L’utilisation de la cryptographie à courbe elliptique garantit un faible coût de calcul tout en permettant une distribution sécurisée des clés de groupe. Dans les deux solutions de sécurité, nous fournissons des preuves formelles et informelles de la sécurité dans le modèle d’attaque défini. Une analyse de l’impact sur la performance et une comparaison avec les solutions existantes sont également menées pour les solutions proposées, montrant que les solutions proposées sont sûres et efficaces et peuvent être utilisées dans de multiples applications IoTThe Internet of Things (IoT) is a diverse network of objects typically interconnected via the Internet. Given the sensitivity of the information exchanged in IoT applications, it is essential to guarantee security and privacy. This problem is aggravated by the open nature of wireless communications, and the power and computing resource limitations of most IoT devices. Existing IoT security solutions are based on centralized architectures, which raises scalability issues and the single point of failure problem, making them susceptible to denial-of-service attacks and technical failures. Blockchain has emerged as an attractive solution to IoT security and centralization issues. Blockchains replicate a permanent, append-only record of all transactions occurring on a network across multiple devices, keeping them synchronized through a consensus protocol. Blockchain implementation may involve high computational and energy costs for devices. Consequently, solutions based on Fog/Edge computing have been considered in the integration with IoT. However, the cost of Blockchain utilization must be optimized, especially in the consensus protocol, which significantly influences the overall system performance. Permissioned Blockchains align better with the requirements of IoT applications than Permissionless Blockchains, due to their high transaction processing rate and scalability. This is because the consensus nodes, i.e., Validators, are known and predetermined. In existing consensus protocols used in Permissioned Blockchains, the Validators are usually a predefined or randomly selected set of nodes, which affects both system performance and fairness among users. The objective of this work is to propose solutions to improve security and privacy within IoT by integrating Blockchain technology, as well as to maximize fairness levels during consensus. The study is organized into two distinct parts: one addresses critical aspects of IoT security and proposes Blockchain-based solutions, while the other part focuses on optimizing fairness among users during the execution of the consensus algorithm on the Blockchain. We present an authentication mechanism inspired by the µTesla authentication protocol, which uses symmetric keys that form a hashchain and achieves asymmetric properties by unveiling the key used a while later. With this mechanism and the use of the Blockchain to store the keys and facilitate authentication, our proposal ensures robust and efficient authentication of devices, without the need for a trusted third party. In addition, we introduce a Blockchain-based key management system for group communications adapted to IoT contexts. The use of Elliptic Curve Cryptography ensures a low computational cost while enabling secure distribution of group keys. In both security solutions, we provide formal and informal proofs of security under the defined attack model. A performance impact analysis and a comparison with existing solutions are also conducted, showing that the proposed solutions are secure and efficient and can be used in multiple IoT applications. The second part of the work proposes an algorithm to select Validator nodes in Permissioned Blockchains maximizing Social Welfare, using α-Fairness as the objective function. A mathematical model of the problem is developed, and a method for finding the solution in a distributed manner is proposed, employing metaheuristic Evolutionary algorithms and a Searchspace partitioning strategy. The security of the proposed algorithm and the quality of the solutions obtained are analyzed. As a result of this work, two security protocols for IoT based on Blockchain are introduced, along with a distributed algorithm for maximizing Social Welfare among users in a Permissioned Blockchain network
19
Akhtar, Sabina. "Vérification formelle d'algorithmes distribués en PlusCal-2." Electronic Thesis or Diss., Université de Lorraine, 2012. http://www.theses.fr/2012LORR0014.
Анотація:
La conception d'algorithmes pour les systèmes concurrents et répartis est subtile et difficile. Ces systèmes sont enclins à des blocages et à des conditions de course et sont par conséquent difficiles à reproduire La vérification formelle est une technique essentielle pour modéliser le système et ses propriétés et s'assurer de sa correction au moyen du model checking. Des langages formels tels TLA+ permettent de décrire des algorithmes compliqués de manière assez concise, mais les concepteurs d'algorithmes trouvent souvent difficile de modéliser un algorithme par un ensemble de formules. Dans ce mémoire nous présentons le langage PlusCal-2 qui vise à allier la simplicité de pseudo-code à la capacité d'être vérifié formellement. PlusCal-2 améliore le langage algorithmique PlusCal conçu par Lamport en levant certaines restrictions de ce langage et en y ajoutant de nouvelles constructions. Notre langage est destiné à la description d'algorithmes à un niveau élevé d'abstraction. Sa syntaxe ressemble à du pseudo-code mais il est tout à fait expressif et doté d'une sémantique formelle. Pour calculer la dépendance conditionnelle pour les algorithmes en PlusCal-2 nous exploitons des informations sur la localité des actions et nous générons des prédicats d'indépendance. Nous proposons également une adaptation d'un algorithme de réduction par ordre partiel dynamique pour une variante du model checker TLC. Enfin, nous proposons une variante d'un algorithme de réduction par ordre partiel statique s'appuyant sur une relation de dépendance constante, et son implantation au sein de TLC. Nous présentons nos résultats expérimentaux et une preuve de correctionDesigning sound algorithms for concurrent and distributed systems is subtle and challenging. These systems are prone to deadlocks and race conditions, and are therefore hard to reproduce. Formal verification is a key technique to model the system and its properties and then perform verification by means of model checking. Formal languages like TLA+ have the ability to describe complicated algorithms quite concisely, but algorithm designers often find it difficult to model an algorithm in the form of formulas. In this thesis, we present PlusCal-2 that aims at being similar to pseudo-code while being formally verifiable. PlusCal-2 improves upon Lamport?s PlusCal algorithm language by lifting some of its restrictions and adding new constructs. Our language is intended for describing algorithms at a high level of abstraction. Finite instances of algorithms described in PlusCal-2 can be verified through the TLC model checker. The second contribution presented in this thesis is a study of partial-order reduction methods using conditional and constant dependency relation. To compute conditional dependency for PlusCal-2 algorithms, we exploit their locality information and present them in the form of independence predicates. We also propose an adaptation of a dynamic partial-order reduction algorithm for a variant of the tlc model checker. As an alternative to partial order reduction based on conditional dependency, we also describe a variant of a static partial-order reduction algorithm for the tlc model checker that relies on constant dependency relation. We also present our results for the experiments along with the proof of correctness
20
Akhtar, Sabina. "Vérification Formelle d'Algorithmes Distribués en PlusCal-2." Phd thesis, Université de Lorraine, 2012. http://tel.archives-ouvertes.fr/tel-00815570.
Анотація:
La conception d'algorithmes pour les systèmes concurrents et répartis est subtile et difficile. Ces systèmes sont enclins à des blocages et à des conditions de course qui peuvent se produire dans des entrelacements particuliers d'actions de processus et sont par conséquent difficiles à reproduire. Il est souvent non-trivial d'énoncer précisément les propriétés attendues d'un algorithme et les hypothèses que l'environnement est supposé de satisfaire pour que l'algorithme se comporte correctement. La vérification formelle est une technique essentielle pour modéliser le système et ses propriétés et s'assurer de sa correction au moyen du model checking. Des langages formels tels TLA+ permettent de décrire des algorithmes compliqués de manière assez concise, mais les concepteurs d'algorithmes trouvent souvent difficile de modéliser un algorithme par un ensemble de formules. Dans ce mémoire nous présentons le langage PlusCal-2 qui vise à allier la simplicité de pseudo-code à la capacité d'être vérifié formellement. PlusCal-2 améliore le langage algorithmique PlusCal conçu par Lamport en levant certaines restrictions de ce langage et en y ajoutant de nouvelles constructions. Notre langage est destiné à la description d'algorithmes à un niveau élevé d'abstraction. Sa syntaxe ressemble à du pseudo-code mais il est tout à fait expressif et doté d'une sémantique formelle. Des instances finies d'algorithmes écrits en PlusCal-2 peuvent être vérifiées à l'aide du model checker tlc. La deuxième contribution de cette thèse porte sur l'étude de méthodes de réduction par ordre partiel à l'aide de relations de dépendance conditionnelle et constante. Pour calculer la dépendance conditionnelle pour les algorithmes en PlusCal-2 nous exploitons des informations sur la localité des actions et nous générons des prédicats d'indépendance. Nous proposons également une adaptation d'un algorithme de réduction par ordre partiel dynamique pour une variante du model checker tlc. Enfin, nous proposons une variante d'un algorithme de réduction par ordre partiel statique (comme alternative à l'algorithme dynamique), s'appuyant sur une relation de dépendance constante, et son implantation au sein de tlc. Nous présentons nos résultats expérimentaux et une preuve de correction.
21
Civit, Pierre. "Spécification des systèmes distribués dynamiques probabilistes sécurisés." Electronic Thesis or Diss., Sorbonne université, 2022. http://www.theses.fr/2022SORUS396.
Анотація:
Cette thèse propose un modèle hiérarchique naturel pour les systèmes distribués dynamiques probabilistes. Le modèle étend les systèmes de transition d'états étiquetés capturant l'intuition d'un objet se déplaçant d'un état à un autre. Le modèle comprend: (1) une opération de composition parallèle, notée || , permettant de représenter un nouvel object A||B issue de l'interaction entre deux objets A et B, (2) une relation de préordre <=, où A<=B signifie que l'objet A implémente l'objet B au sens d'une sémantique observationnelle, (3) la propriété de composabilité pour <= , c'est-à-dire A <= B implique C||A <= C||B, (4) une structure hiérarchique, c'est-à-dire qu'un système X, composé d'objets interagissant les uns avec les autres et pouvant rejoindre et quitter le système dynamiquement, est lui aussi un objet du modèle. De plus, la thèse discute des conditions pour obtenir (5) La monotonicité (avec <=) de la création/destruction dynamique d’objets, c'est-à-dire que si (i) A <= B et (ii) X_A et X_B ne diffèrent que par le fait que X_A crée et détruit dynamiquement l'objet A au lieu de créer et détruire dynamiquement l'objet B comme le fait X_B, alors (iii) X_A <= X_B. Le modèle est décliné en plusieurs variantes: asynchrone, temporelle, bornée et permet une méthodologie modulaire de conception basée uniquement sur la notion de comportement observable de l'extérieurThis thesis proposes a natural hierarchical model for dynamic probabilistic distributed systems. The model extends in an intuitive way the labeled transition systems that best capture the intuition of an object moving from one state to another. The model consists of 3 essential ingredients: (1) a parallel composition operation, noted ||, allowing to represent a new object A||B resulting from the interaction between two objects A and B, (2) a pre-order relation <=, where A <= B means that the object A implements the object B in the sense of an observational semantics, (3) the composability property for <=, that is A <= B implies C||A <= C||B, (4) a hierarchical structure, i.e. a system X, composed of objects interacting with each other and able to join and leave the system dynamically, is also an object of the model. Furthermore, the thesis discusses the conditions to obtain (5) the monotonicity (with <=) of dynamic creation/destruction of objects, i.e., if (i) A <= B and (ii) X_A and X_B differ only by the fact that X_A dynamically creates and destroys the object A instead of dynamically creating and destroying the object B as X_B does, then (iii) X_A <= X_B. The model is declined in several variants: asynchronous, timed, bounded and allows a modular design and a refinement methodology based only on the notion of externally observable behavior
22
Bui, Marc. "Étude comportementale d'algorithmes distribués de contrôle." Paris 11, 1989. http://www.theses.fr/1989PA112242.
Анотація:
Cette thèse étudie les problèmes de contrôle qui se posent lorsqu'on veut gérer des réseaux de processeurs à mémoires locales ou machines distribuées. Le chapitre 1 a pour objet la mise en évidence de l'expression de problèmes distribués sous forme d'équations à l'aide du concept de point fixe qui offre une vision unificatrice de l'algorithmique distribuée. Le chapitre 2 propose une modélisation markovienne pour représenter localement les processus distribués et globalement les relations s'établissant entre ces processus. L'intérêt théorique et la pertinence de ce modèle markovien sont prouvés par son application à plusieurs problèmes: en effet, il permet de résoudre de façon satisfaisante et complète le problème du "dîner des philosophes" (chapitre 9), celui de l'exclusion mutuelle (chapitre 4) et celui de l'inter blocage (chapitre 5) en définissant une famille de de règles de bon fonctionnement. Dans chacun de ces 3 chapitres, sont traitées les implications des comportements locaux sur le comportement global et le réglage des paramètres du modèle afin d'obtenir un fonctionnement optimal des algorithmes distribués (selon des critères adéquats). Dans ces études, l'équité se révèle avoir un rôle important ct dans le chapitre 6, cette notion est étudiée après avoir été mis en évidence par des expériences de programmation en Occam sur réseau de Transputers. Enfin, le chapitre 7 présente l'application du calcul diffusant à la résolution du problème de détection de situations stables exprimées par des équations de point-fixe.
23
Sidi, Bah Aladé Habib. "Algorithmes distribués dans les réseaux hétérogènes et autonomes." Phd thesis, Université d'Avignon, 2012. http://tel.archives-ouvertes.fr/tel-00879973.
Анотація:
La diversité croissante des différents agents constituant les réseaux de communication actuels ainsi que la capacité accrue des technologies concurrentes dans l'environnement réseau a conduit à la prise en compte d'une nouvelle approche distribuée de la gestion du réseau. Dans cet environnement réseau évolué, le besoin en accroissement de la bande passante et en ressources rares, s'oppose à la réduction de la consommation énergétique globale.Dans notre travail nous nous intéressons à l'application de mécanismes distribués et de méthodes d'apprentissages visant à introduire d'avantage d'autonomie dans les réseaux hétérogènes, mobiles en particulier, tout en améliorant les performances par rapport aux débits et à la qualité de service. Notre étude se concentre principalement sur l'élaboration de mécanismes distribués stochastiques et énergétiquement efficaces en profitant des capacités de calcul de tous les agents et entités du réseau. Divers outils de la théorie des jeux nous permettent de modéliser et d'étudier différents types de systèmes dont la complexité est induite par la grande taille, l'hétérogénéité et le caractère dynamique des interconnexions. Plus spécifiquement, nous utilisons des outils d'apprentissage par renforcement pour aborder des questions telles que l'attachement distribué des utilisateurs permettant une gestion dynamique, décentralisée et efficace des ressources radio. Nous combinons ensuite les procédures de sélection d'accès à des méthodes d'optimisation distribuées du type gradient stochastique, pour adresser le problème de coordination des interférences intercellulaires (ICIC) dans les réseaux LTE-A. Cette approche se base sur un contrôle de puissance dynamique conduisant à une réutilisation fractionnaire des fréquences radios. Par ailleurs nous adressons dans les réseaux décentralisés non-hiérarchiques, plus précisément les réseaux tolérants aux délais (DTNs), des méthodes décentralisées liées à la minimisation du délai de transmission de bout en bout. Dans ce cadre nous nous intéressons, en outre des équilibres de Nash, à la notion d'équilibre évolutionnairement stables dans différents contextes de jeux évolutionnaires, jeux évolutionnaires décisionnels markoviens et jeux de minorité. Enfin, la majeure partie du travail effectué se rattachant aux tests et validations par simulations,nous présentons plusieurs éléments d'implémentations et d'intégrations liés à la mise en place de plateformes de simulations et d'expérimentations.
24
Debrat, Henri. "Certification formelle de la correction d'algorithmes distribués avec erreurs de transmission." Thesis, Université de Lorraine, 2013. http://www.theses.fr/2013LORR0268.
Анотація:
La propension des systèmes informatiques à subir des défaillances matérielles est à l'origine d'une recherche abondante afin de concevoir des systèmes dits tolérants aux pannes. Le procédé couramment retenu consiste à procéder à des réplications, donnant alors naissance à ce que l'on nomme un système distribué. La question se pose alors de savoir si l'on peut garantir que les multiples copies sont cohérentes entre elles. Ainsi, la recherche d'un accord devient-elle un problème à résoudre, à portée paradigmatique : le Consensus. Or, la complexité des algorithmes de Consensus rend la tache ardue : il n'est donc pas rare que l'on commette des erreurs lors de leur conception. De là découle l'idée, développée depuis plus de trente ans, de recourir à des procédés de vérification mécanique des algorithmes et de leurs preuves de correction. Ces procédés prennent place parmi ce que l'on désigne usuellement comme étant des méthodes formelles. C'est à la croisée des recherches en algorithmique distribuée et en méthodes formelles que se situent nos travaux. Plus spécifiquement, il s'agit de faire usage d'un logiciel de certification formelle, Isabelle/HOL, afin de garantir l'exactitude des preuves de correction d'algorithmes de Consensus exprimés dans un cadre formel uniforme du nom de Heard-Of, proposé en 2009 par Charron-Bost et Schiper. Nous montrons que, du fait de leur expression dans un même cadre formel, et du fait de leur proximité, suivant les cas, soit de conception (nombre de rondes, recours à des mécanismes de vote, ...) soit de forme syntaxique, soit d'hypothèses de fonctionnement (synchronisme partiel, ...), ces algorithmes présentent des preuves dont une part conséquente d?arguments sont communs. Cela permet de copier certains d'entre eux d'une preuve à l'autre, afin de réduire l'effort de certification : ces arguments peuvent alors être automatiquement évalués par la machine pour chacun d'entre eux, l'utilisateur n'ayant à intervenir que là où celle-ci est en peine, c'est-à-dire lorsque les différences algorithmiques induisent qu'il faille réviser les détails de l'argumentation. L'exposé que nous faisons de la certification que nous avons effectuée pour six algorithmes distribués dédiés à la résolution du problème du Consensus illustre cette démarche. Par conséquent, nous présentons d'abord les portions communes des démonstrations, puis détaillons ce qui est propre à chacune, l'objectif n'étant pas de permettre une lecture linéaire de chaque démonstration mais de mettre en évidence notre propositionComputer systems fail. Whatever the reason of these failures, it has been a widespread approach to try and increase the faults-tolerance of a computer system through its replication. The resulting system is said to be a distributed one, in which replicas have to be kept consistent with each others. Hence, reaching agreement, and Consensus in particular, becomes the problem to solve - indeed, the paradigm. Solving Consensus (under various assumptions) is a hard task : algorithms designed on this purpose are subtle and proving their being correct is error-prone - whenever they are, which occasionally appears not to be the case. For more that thirty years, researchers interested in what is called Formal Methods have been working on mechanizing the verification process, in order to increase confidence in the correctness of (distributed) algorithms. The work we present here is at the intersection of distributed algorithms and formal methods. We use the Isabelle/HOL software to certify the correctness proof of various Consensus algorithms expressed in a uniform framework based on the Heard-Of Model, introduced by Charron-Bost and Schiper in 2009. Expressed in a common model, these algorithms, which, depending on the case, share some common mecanisms (number of steps, intermediate votes, ...), some elements of syntax, or types of assumptions (partial synchronism...), can be proved using some common arguments. As a consequence, the certification effort can be reduced by copying some intermediate lemmas from one proof to another and let the computer automatically parse them until some manual adaptation is required. This lead to the idea of certifying the correctness of multiple algorithms all together, instead of proving them one after the other, as one would do on paper in a traditional way. The effort of translation in the formal language of the proof assistant is then possibly reduced. Of course, each proof will also contain specific arguments, which will have to be isolated and translated into the software. Here, we illustrate this proposition through the presentation of formal certificates of correctness for six Consensus algorithms. As a consequence, on should not expect to find here a comprehensive linear presentation of each proof : we first show the arguments shared by multiple proofs, followed by those which are specific to each o them
25
Thomé, Emmanuel. "Algorithmes de calcul de logarithmes discrets dans les corps finis." Phd thesis, Ecole Polytechnique X, 2003. http://tel.archives-ouvertes.fr/tel-00007532.
Анотація:
Le calcul de logarithmes discrets est un problème central en cryptologie. Lorsqu'un algorithme sous-exponentiel pour résoudre ce problème existe, le cryptosystème concerné n'est pas nécessairement considéré comme disqualifié, et il convient d'actualiser avec soin l'état de l'art de la cryptanalyse. Les travaux de ce mémoire s'inscrivent dans cette optique. Nous décrivons en particulier comment nous avons atteint un record de calculs de logarithmes discrets: \GFn(607).Dans une première partie, nous exposons les différentes améliorations que nous avons apportées à l'algorithme de Coppersmith pour le calcul de logarithmes discrets en caractéristique 2. Ces améliorations ont rendu possible le record que nous avons atteint. La portée de ce calcul dépasse
le simple cadre des corps finis, à cause de l'existence de la réduction MOV d'une part, et de la récente introduction des cryptosystèmes fondés sur l'identité.
On s'intéresse plus en détail, dans une seconde partie du mémoire, au problème classique de la résolution d'un système linéaire creux défini sur un corps fini, porté aux limites de ce que la technologie (théorique et pratique) permet. Nous montrons comment une amélioration substantielle de l'algorithme de Wiedemann par blocs a rendu celui-ci compétitif pour la résolution d'un grand système linéaire creux sur \GF p.
Une partie de ce mémoire est consacrée au point de vue de l'expérimentateur, grand utilisateur de moyens de calcul, de la surcharge de travail humain que cela impose, et des constatations que cette position amène.
26
Lambein, Patrick. "Consensus de moyenne dans les réseaux dynamiques anonymes : Une approche algorithmique." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX103.
Анотація:
L’avènement de composants électroniques compacts et bon marché présage d’une diversification rapide d’applications dans lesquelles des agents autonomes en réseau travaillent à réaliser un objectif commun. Ces tâches complexes, en dépit de leur diversité, dépendent de la maîtrise d’un petit nombre de primitives de coordination, dont l’implémentation programmatique par des agents à faible puissance et capacité calculatoire constitue l’un des enjeux majeurs du développement de telles applications réparties. Parmi ces dernières, citons par exemple la coordination du mouvement de réseaux mobiles et véhiculaires, l’aggrégation et le traitement distribué de mesures relevées par des réseaux de capteurs, et le a répartition de charge en temps réel au sein d’un réseau fournissant un service à grande échelle. L’implémentation distribuée de telles primitives se doit de répondre à différentes contraintes, qui ne résultent pas toutes de la nature numérique des entités constitutives du réseau ; en conséquence, l’étude théorique de ces primitives s’applique à la modélisation de comportements complexes de systèmes étudiés par les sciences naturelles, tels que les mouvements collectifs animaliers ou le système nerveux.Cette monographie traite spécifiquement d’algorithmes distribués qui réalisent le calcul asymptotique de la moyenne de valeurs initialement détenues par les agents d’un réseau dont les liens de communication sont amenés à changer au cours du temps, ceci en l’absence de coordination centralisée. Ces algorithmes doivent être implémentables localement, en n’exploitant que l’information qui peut être collectée par les agents lors de leurs interactions sur le réseau, et en l’absence de mécanisme particulier pour marquer le départ, tel qu’un signal global ou un agent initiateur.Nous développons des algorithmes qui réalisent un tel consensus de moyenne sur des réseaux dynamiques présentant certaines propriétés locales. Ces algorithmes sont simples à décrire, légers à implémenter, et opèrent en temps polynomial en le nombre d’agents.Sur des réseaux présentant des interactions bidirectionnelles, nous fournissons un algorithme déterministe qui réalise le calcul asymptotique de la moyenne dès lors que le réseau ne se sépare jamais de façon permanente. Pour le cas plus général d’interactions asymétriques, nous présentons un algorithme Monte Carlo stabilisant qui est efficace en termes de complexité spatiale et opère en temps linéaire. Ce dernier algorithme admet une extension dont les exécutions terminent en tolérant un départ asynchrone des agents. Nos algorithmes sont à considérer en regard de résultats et de méthodes qui reposent sur une information globale fournie externalement aux agents, sur des hypothèses de brisure initiale de symétrie, ou qui exploitent une topologie particulière et ne se généralisent pas à des réseaux quelconques. Dans ce contexte, nous contribuons des algorithmes dont les conditions de validité sont purement locales dans le temps et l’espace : pour le modèle d’interactions bidirectionnelles, nous montrons que le calcul asymptotique de la moyenne est réalisable par des agents déterministes, là où pour le modèle général nous fournissons des algorithmes randomisés dont les performances asymptotiques sont bien meilleures que celles de protocoles à information complète et robustes aux départs asynchrones.Par-delà l’intérêt immédiat à l’obtention d’algorithmes efficaces implémentables, notre étude s’inscrit dans un effort de cartographie des limites que la localité des interactions impose aux applications répartiesCompact and cheap electronic components announce the near-future development of applications in which networked systems of autonomous agents are made to carry over complex tasks. These, in turn, depend on a small number of coordination primitives, which need to be programmatically implemented into potentially low-powered, and computationally limited, agents.Such applications include for example the coordination of the collective motion of mobile and vehicular networks, the distributed aggregation and processing of data measured locally in sensor networks, and the on-line repartition of processing load in the computer farms powering wide-scale services. As they address constraints that are not specific to the digital nature of the network such primitives also serve to model complex behavior of natural systems, such as flocks and neural networks.This monograph focuses on providing distributed algorithms that asymptotically compute the average of initial values, initially present at each agent of a networked system with time-varying communication links and in the absence of centralized control. Additionally, we consider the weaker problem of getting the agents to asymptotically agree on any value within the initial bounds. We focus on locally implementable algorithms, which leverage no information beyond what the agents can acquire by themselves, and which need no bootstrapping mechanism like a global start signal or a leader agent.We provide distributed average consensus algorithms that operate over dynamic networks given different local assumptions. These algorithms are computationally simple and operate in polynomial time in the number of agents.For bidirectional communications, we give a deterministic algorithm which asymptotically computes the average as long as the network never becomes permanently disconnected. For the general case of asymmetric communications, we provide a stabilizing Monte Carlo algorithm that is efficient in bandwidth and memory and operates in linear time, along with an extension by which the algorithm can be made to uniformly terminate over any connected network in which agents may start asynchronously.This contrasts with a plethora of results and techniques in which agents are provided external information – the size of the system, a bound over their degree, – helped with exogenous symmetry breaking – a leader agent, unique identifiers, – or where the network is expected to conform to a specific shape – a ring, a a complete network, a regular graph. Indeed, because very different networks may look alike to the agents, they are limited in what they can learn locally, and many functions are impossible to compute in a fully distributed manner without assuming some structure in the network or additional symmetry-breaking device. Given these stringent constraints, our contribution is to offer algorithms whose validity depends uniquely on local and instantaneous conditions. In the bidirectional model, we show that anonymous deterministic agents can asymptotically compute the average in polynomial time. For the general model of directed interactions, we allow agents to consult random oracles. Under those conditions, full information protocols are capable of solving any problem, and so we focus on the spatial complexity and tolerance to a lack of initial coordination in the agents, while offering stronger termination guarantees than in the bidirectional case. Beyond the fact that locally implementable algorithms are eminently desirable, our study contributes to mapping the limits that local interactions impose on networks
27
Debrat, Henri. "Certification formelle de la correction d'algorithmes distribués avec erreurs de transmission." Electronic Thesis or Diss., Université de Lorraine, 2013. http://www.theses.fr/2013LORR0268.
Анотація:
La propension des systèmes informatiques à subir des défaillances matérielles est à l'origine d'une recherche abondante afin de concevoir des systèmes dits tolérants aux pannes. Le procédé couramment retenu consiste à procéder à des réplications, donnant alors naissance à ce que l'on nomme un système distribué. La question se pose alors de savoir si l'on peut garantir que les multiples copies sont cohérentes entre elles. Ainsi, la recherche d'un accord devient-elle un problème à résoudre, à portée paradigmatique : le Consensus. Or, la complexité des algorithmes de Consensus rend la tache ardue : il n'est donc pas rare que l'on commette des erreurs lors de leur conception. De là découle l'idée, développée depuis plus de trente ans, de recourir à des procédés de vérification mécanique des algorithmes et de leurs preuves de correction. Ces procédés prennent place parmi ce que l'on désigne usuellement comme étant des méthodes formelles. C'est à la croisée des recherches en algorithmique distribuée et en méthodes formelles que se situent nos travaux. Plus spécifiquement, il s'agit de faire usage d'un logiciel de certification formelle, Isabelle/HOL, afin de garantir l'exactitude des preuves de correction d'algorithmes de Consensus exprimés dans un cadre formel uniforme du nom de Heard-Of, proposé en 2009 par Charron-Bost et Schiper. Nous montrons que, du fait de leur expression dans un même cadre formel, et du fait de leur proximité, suivant les cas, soit de conception (nombre de rondes, recours à des mécanismes de vote, ...) soit de forme syntaxique, soit d'hypothèses de fonctionnement (synchronisme partiel, ...), ces algorithmes présentent des preuves dont une part conséquente d?arguments sont communs. Cela permet de copier certains d'entre eux d'une preuve à l'autre, afin de réduire l'effort de certification : ces arguments peuvent alors être automatiquement évalués par la machine pour chacun d'entre eux, l'utilisateur n'ayant à intervenir que là où celle-ci est en peine, c'est-à-dire lorsque les différences algorithmiques induisent qu'il faille réviser les détails de l'argumentation. L'exposé que nous faisons de la certification que nous avons effectuée pour six algorithmes distribués dédiés à la résolution du problème du Consensus illustre cette démarche. Par conséquent, nous présentons d'abord les portions communes des démonstrations, puis détaillons ce qui est propre à chacune, l'objectif n'étant pas de permettre une lecture linéaire de chaque démonstration mais de mettre en évidence notre propositionComputer systems fail. Whatever the reason of these failures, it has been a widespread approach to try and increase the faults-tolerance of a computer system through its replication. The resulting system is said to be a distributed one, in which replicas have to be kept consistent with each others. Hence, reaching agreement, and Consensus in particular, becomes the problem to solve - indeed, the paradigm. Solving Consensus (under various assumptions) is a hard task : algorithms designed on this purpose are subtle and proving their being correct is error-prone - whenever they are, which occasionally appears not to be the case. For more that thirty years, researchers interested in what is called Formal Methods have been working on mechanizing the verification process, in order to increase confidence in the correctness of (distributed) algorithms. The work we present here is at the intersection of distributed algorithms and formal methods. We use the Isabelle/HOL software to certify the correctness proof of various Consensus algorithms expressed in a uniform framework based on the Heard-Of Model, introduced by Charron-Bost and Schiper in 2009. Expressed in a common model, these algorithms, which, depending on the case, share some common mecanisms (number of steps, intermediate votes, ...), some elements of syntax, or types of assumptions (partial synchronism...), can be proved using some common arguments. As a consequence, the certification effort can be reduced by copying some intermediate lemmas from one proof to another and let the computer automatically parse them until some manual adaptation is required. This lead to the idea of certifying the correctness of multiple algorithms all together, instead of proving them one after the other, as one would do on paper in a traditional way. The effort of translation in the formal language of the proof assistant is then possibly reduced. Of course, each proof will also contain specific arguments, which will have to be isolated and translated into the software. Here, we illustrate this proposition through the presentation of formal certificates of correctness for six Consensus algorithms. As a consequence, on should not expect to find here a comprehensive linear presentation of each proof : we first show the arguments shared by multiple proofs, followed by those which are specific to each o them
28
Boussaton, Octave. "Application de la théorie des jeux à l'optimisation du routage réseau - solutions algorithmiques." Phd thesis, Université Henri Poincaré - Nancy I, 2010. http://tel.archives-ouvertes.fr/tel-00605791.
Анотація:
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.
29
Malvault, Willy. "Vers une architecture pair-à-pair pour l'informatique dans le nuage." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00633787.
Анотація:
Avec l'émergence de l'informatique dans les nuages, une nouvelle approche consiste à externaliser des tâches de calcul, de façon à réduire les coûts d'hébergement et à augmenter la flexibilité des systèmes. L'infrastructure actuelle des services permettant cette externalisation repose sur l'utilisation de centres de traitement de données centralisés, qui sont dédiés à l'approvisionnement de ressources de calcul. Dans cette thèse, nous étudions la possibilité de fournir de tels services en utilisant une infrastructure pair-à-pair, c'est-à-dire une infrastructure totalement décentralisée pouvant être déployée sur une fédération de noeuds de calcul hétérogénes et de provenances diverses. Nous nous focalisons sur le problème de l'allocation des noeuds et présentons Salute, un service d'allocation de noeuds, qui organise les noeuds en réseaux virtuels non-structurés et repose sur des mécanismes de prédiction de disponibilité pour assurer, avec une grande probabilité, que les requêtes d'allocation sont satisfaites dans le temps, malgré le dynamisme de l'environnement hôte. Pour ce faire, le service Salute repose sur la collaboration de plusieurs protocoles pair-à-pair appartenant à la catégorie des protocoles épidémiques. Afin de valider nos propositions, nous évaluons Salute en utilisant des traces provenant d'un échantillonnage de plusieurs systèmes pair-à-pair de référence.
30
Maviel, Pierre. "Definition de classes d'environnements reseaux pour la simulation d'algorithmes distribues." Paris 6, 1987. http://www.theses.fr/1987PA066519.
Анотація:
Presentation de l'interet apporte a l'algorithmique distribuee, par une homogeneisation des hypotheses sur les proprietes comportementales et structurelles de l'environnement de communication. L'objectif recherche est de permettre, a partir d'un nombre restreint d'hypotheses, la classification d'algorithmes distribues afin de faciliter leurs comparaisons
31
Casteigts, Arnaud. "Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hoc - Calculs locaux et réétiquetages de graphes dynamiques." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2007. http://tel.archives-ouvertes.fr/tel-00193181.
Анотація:
Les réseaux mobiles ad hoc sont par nature instables et imprévisibles. De ces caractéristiques découle la difficulté à concevoir et analyser des algorithmes distribués garantissant certaines propriétés. C'est sur ce point que porte la contribution majeure de cette thèse. Pour amorcer cette étude, nous avons étudié quelques problèmes fondamentaux de l'algorithmique distribuée dans ce type d'environnement. Du fait de la nature de ces réseaux, nous avons considéré des modèles de calculs locaux, où chaque étape ne fait collaborer que des n\oe uds directement voisins. Nous avons notamment proposé un nouveau cadre d'analyse, combinant réétiquetages de graphes dynamiques et graphes évolutifs (modèle combinatoire pour les réseaux dynamiques). Notre approche permet de caractériser les conditions de succès ou d'échec d'un algorithme en fonction de la dynamique du réseau, autrement dit, en fonction de conditions nécessaires et/ou suffisantes sur les graphes évolutifs correspondants. Nous avons également étudié la synchronisation sous-jacente aux calculs, ainsi que la manière dont une application réelle peut reposer sur un algorithme de réétiquetage. Un certain nombre de logiciels ont également été réalisés autour de ces travaux, notamment un simulateur de réétiquetage de graphes dynamiques et un vérificateur de propriétés sur les graphes évolutifs.
32
Lebhar, Emmanuelle. "Algorithmes de routage et modèles aléatoires pour les graphes petits mondes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2005. http://tel.archives-ouvertes.fr/tel-00011646.
Анотація:
L'objet de cette thèse est l'étude des aspects algorithmiques de l'effet petit monde dans les grands réseaux d'interaction.Les observations expérimentales ont montré que les grands réseaux d'interactions (sociales, informatiques, biologiques), présentaient des propriétés macroscopiques communes. Une d'elles est l'effet petit monde qui consiste en l'existence de chemins très courts entre toutes les paires de noeuds qui peuvent être découverts en n'utilisant qu'une vue locale du réseau. Nous nous intéressons à cette caractéristique algorithmique de l'effet petit monde, à son application au routage informatique décentralisé, et à son émergence dans les réseaux réels.Nous proposons un nouvel algorithme de routage décentralisé sur le modèle aléatoire de petit monde de Kleinberg, qui calcule des chemins de longueur O(log n.(loglog n)^2), asymptotiquement plus courts que ceux des algorithmes existants (en O((log n)^2)). Cet algorithme pourrait également s'appliquer aux réseaux pair-à-pair. Nous précisons cette étude en comparant les charges induites pas les différents algorithmes proposés sur ce modèle.En tentant d'exhiber les caractéristiques minimales d'un graphe qui permettent de l'augmenter en un petit monde par l'ajout de raccourcis aléatoires, nous proposons un nouveau modèle de petit monde qui généralise celui de Kleinberg. Il s'agit d'ajouter une distribution de liens dépendant de la taille des boules de la métrique des distance sous-jacente. Ce modèle peut par ailleurs être étendu simplement pour produire toute distribution des degrés, dont en particulier la fameuse loi de puissance. Enfin, nous proposons le premier schéma distribué qui permette de transformer un réseau de diamètre quelconque en petit monde en ajoutant un seul nouveau lien par noeud, il s'agit d'un premier pas vers la compréhension de l'émergence naturelle du phénomène dans les réseaux réels.
33
Fortin, Pierre. "Algorithmique hiérarchique parallèle haute performance pour les problèmes à N-corps." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2006. http://tel.archives-ouvertes.fr/tel-00135843.
Анотація:
Cette thèse porte sur la méthode dite « méthode multipôle rapide » qui résout hiérarchiquement le problème à N-corps avec une complexité linéaire pour n'importe quelle précision. Dans le cadre de l'équation de Laplace, nous souhaitons pouvoir traiter efficacement toutes les distributions de particules rencontrées en astrophysique et en dynamique moléculaire.Nous étudions tout d'abord deux expressions distinctes du principal opérateur (« multipôle-to-local ») ainsi que les bornes d'erreur associées. Pour ces deux expressions, nous présentons une formulation matricielle dont l'implémentation avec des routines BLAS (Basic Linear Algebra Subprograms) permet d'améliorer fortement l'efficacité de calcul. Dans la gamme de précisions qui nous intéresse, cette approche se révèle plus performante que les améliorations existantes (FFT, rotations et ondes planes), pour des distributions uniformes ou non.
Outre une nouvelle structure de données pour l'octree sous-jacent et des contributions algorithmiques à la version adaptative, nous avons aussi efficacement parallélisé notre méthode en mémoire partagée et en mémoire distribuée. Enfin, des comparaisons avec des codes dédiés justifient l'intérêt de notre code pour des simulations en astrophysique.
34
Blin, Lélia. "Algorithmes auto-stabilisants pour la construction d'arbres couvrants et la gestion d'entités autonomes." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2011. http://tel.archives-ouvertes.fr/tel-00847179.
Анотація:
Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce document s'intéresse à l'approche auto-stabilisante qui vise à concevoir des algorithmes se ''réparant d'eux-même ' en cas de fautes transitoires, c'est-à-dire de pannes impliquant la modification arbitraire de l'état des processus. Il se focalise sur deux contextes différents, couvrant la majeure partie de mes travaux de recherche ces dernières années. La première partie du document est consacrée à l'algorithmique auto-stabilisante pour les réseaux de processus. La seconde partie du document est consacrée quant à elle à l'algorithmique auto-stabilisante pour des entités autonomes (agents logiciels, robots, etc.) se déplaçant dans un réseau.
35
Bernard, Thibault. "Marches aléatoires et mot circulant, adaptativité et tolérance aux pannes dans les environnements distribués." Phd thesis, Université de Reims - Champagne Ardenne, 2006. http://tel.archives-ouvertes.fr/tel-00143600.
Анотація:
Nous proposons dans ces travaux une étude des marches aléatoires dans l'algorithmique distribuée pour les réseaux dynamiques. Nous montrons dans un premier temps que les marches aléatoires sont un outil viable pour la conception d'algorithmes distribués. Ces algorithmes reposent principalement sur les trois propriétés fondamentales des marches aléatoires (Percussion, Couverture, Rencontre). Nous fournissons une méthode qui évalue
le temps ́ecoulé avant que ces trois propriétés soient vérifiées. Cela nous permet d'évaluer de la complexité de nos algorithmes. Dans un second temps, nous proposons l'utilisation d'un jeton circulant aléatoirement sous forme de mot circulant afin de collecter sur ce jeton des informations topologiques. Ces informations permettent la construction et la maintenance d'une structure couvrante du réseau de communication. Ensuite, nous
avons utilisé cette structure pour concevoir un algorithme de circulation de jeton tolérant aux pannes pour les environnements dynamiques. Cet algorithme a la particularité d'être complètement décentralisé. Nous proposons dans un dernier temps d'adapter notre circulation de jeton pour proposer une solution au problème d'allocation de ressources dans les réseaux ad-hoc.
36
Simon, Gwendal. "Conception et réalisation d'un système pour environnement virtuel massivement partagé." Rennes 1, 2004. http://www.theses.fr/2004REN10158.
Анотація:
Cette thèse décrit Solipsis, un système permettant à un nombre illimité de participants de s'immerger dans un monde virtuel. Il est basé sur un réseau de pairs. Toutes les entités virtuelles sont des pairs qui collaborent pour le maintien de propriétés globales permettant à un monde virtuel unique d'exister. Dans une première partie, nous présentons les algorithmes distribués de Solipsis. Puis, la deuxième partie décrit l'étude de deux services fondamentaux pouvant enrichir le monde virtuel : un mécanisme de recherche et un service d'éditeur/abonné.
37
Pigné, Yoann. "Modélisation et traitement décentralisé des graphes dynamiquesApplication aux réseaux mobiles ad hoc." Phd thesis, Université du Havre, 2008. http://tel.archives-ouvertes.fr/tel-00371962.
Анотація:
Les graphes dynamiques sont un outil de plus en plus utilisé dans des contextes variés où il s'avère nécessaire de modéliser des environnements changeants ou incertains. Les modèles aujourd'hui proposés sont dédiés à ces applications précises. Il n'existe pas de modèle général reprenant, hors de tout contexte applicatif, ces caractéristiques. D'autre part la résolution de problèmes liés à ces environnements dynamiques et incertains est problématique. Nous proposons, ici, la formalisation d'un modèle général de graphe dynamique. Nous étudions la résolution de problèmes dans ces graphes à l'aide de méthodes inspirées de mécanismes d'intelligence collective.
Les modèles proposés sont validés dans le contexte applicatif des réseaux mobiles ad hoc. Une approche originale de construction et de maintien de chemins de communication sous plusieurs contraintes est proposée. Le problème de la construction et du maintien d'une forêt couvrante dans un réseau mobile ad hoc est également étudié.
38
Maamra, Khaled. "Algorithmes auto-stabilisants efficaces pour les graphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLV065/document.
Анотація:
Le projet scientifique dans lequel s’inscrit ma thèse a pour objectif l’élaboration d’algorithmes distribués et efficaces pour les réseaux informatiques. Ce projet vise une catégorie particulière des algorithmes distribués, dits auto-stabilisants. Il s’agit d’algorithmes ayant pour propriété de retrouver un comportement correct suite à une panne dans le réseau et ce, sans aucune intervention humaine. Le travail effectué en collaboration avec mes directeurs de thèse s’est concentré, plus précisément, autour des problèmes de couplage, de cliques et des paradigmes de publications-souscriptions dans ce domaine de l’informatique théorique. Dans un premier temps on a traité le problème du couplage maximal dans sa version anonyme, en fournissant un algorithme auto-stabilisant probabiliste et efficace. Ces travaux sont parus dans le journal PPL. De plus, on s’est intéressé au problème du couplage dans sa version maximum identifiée. Son travail améliore le dernier algorithme présent dans la littérature pour l’approximation de ce type de couplage au 2/3 de la solution optimale. Ces travaux sont parus dans une conférence internationale OPODIS. Par ailleurs, j'ai eu l’opportunité de collaborer en Allemagne avec Prof. Volker Turau au sein du groupe de télématique de l’Université technique de Hambourg. Le cadre de cette collaboration a été les algorithmes auto-stabilisants pour les paradigmes de publication-souscription. Cela a abouti à un algorithme efficace pour la version en canal de ce problème, introduisant la notion de raccourci pour le routage de messages dans ces paradigmes. Les résultats ont fait l’objet d’un Brief Announcement et d’un papier, publiés dans des conférences internationales, SSS et NetSyS. J'ai aussi bénéficié d’une collaboration avec Mr. Gerry Siegemund qui a été accueilli au laboratoire d’Informatique de l’École Polytechnique. Il a été question de trouver un algorithme efficace et auto-stabilisant pour la partition d’un réseau en cliques. Cette collaboration a eu pour résultat un algorithme pour le problème améliorant le dernier en date. Ce résultat est en cours de rédaction pour soumission à une conférence internationaleThe main focus of my thesis is the design of an efficient kind of distributed algorithms, known as: Self-stabilizing. These algorithms have the property to recover from faults in the environment they're executed in, and this without any human intervention. Recovering here, means converging toward a pre-defined, correct configuration. In this setting, I was mainly interested by the problems of matching in graphs, clique partitions and publication subscription paradigms. For the maximal version of the matching problem in anonymous graphs, we achieved a more efficient randomized, self-stabilizing algorithm. This work is published in a journal version in PPL. The maximum version of the same problem, but in an identified setting, led to the design of an efficient self-stabilizing algorithm that approximates the optimal solution up to the 2/3. This result was published at OPODIS. During a research visit at TUHH, Hamburg, Germany. Together with Pr. Volker Turau we tackled the problem of self-stabilizing publish/subscribe paradigms. This led to an algorithm introducing the new notion of short-cuts in this type of structures and was published under a brief announcement and a regular paper at SSS and NetSyS. In collaboration with Mr. Siegemund, then a visiting researcher at LIX, École Polytechnique, we worked on an efficient self-stabilizing algorithm for clique partitions. This work is still in progress and in preparation for an eventual publication
39
Hanusse, Nicolas. "Navigation dans les grands graphes." Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2009. http://tel.archives-ouvertes.fr/tel-00717765.
40
Duboux, Thibault. "Régulation dynamique du partitionnement de données sur machines parallèles à mémoire distribuée." Lyon, École normale supérieure (sciences), 1996. http://www.theses.fr/1996ENSL0009.
Анотація:
Le fil conducteur de cette thèse est l'équilibrage de charge : après un état de l'art sur l'équilibrage à toutes les étapes, de l'élaboration à l'exécution, des implantations sur ordinateurs parallèles à mémoire distribuée, nous proposons une strategie pour maintenir equilibre le partitionnement des donnees pour des problemes dynamiques et irreguliers. Cette strategie est particulierement adaptee dans des applications gerant des donnees complexes soumises a des requetes de mise a jour et de consultation. Elle se caracterise par sa tres faible influence sur le comportement de l'application. Cette strategie a ete appliquee sur des machines synchrones et asynchrones. Une machine dictionnaire synchrone a ainsi ete rendue modulaire grace a l'ajout de l'equilibrage. Une machine dictionnaire a egalement pu etre implantee sur un ordinateur asynchrone, cela servant de point de depart pour des applications en bases de donnees. Enfin, le probleme de l'arrangement d'un ensemble de segments dans le plan a permis de valider la strategie d'equilibrage pour des applications complexes
41
Malvaut-Martiarena, Willy. "Vers une architecture pair-à-pair pour l'informatique dans le nuage." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM044/document.
Анотація:
Avec l'émergence de l'informatique dans les nuages, une nouvelle approche consiste à externaliser des tâches de calcul, de façon à réduire les coûts d'hébergement et à augmenter la flexibilité des systèmes. L'infrastructure actuelle des services permettant cette externalisation repose sur l'utilisation de centres de traitement de données centralisés, qui sont dédiés à l'approvisionnement de ressources de calcul. Dans cette thèse, nous étudions la possibilité de fournir de tels services en utilisant une infrastructure pair-à-pair, c'est-à-dire une infrastructure totalement décentralisée pouvant être déployée sur une fédération de noeuds de calcul hétérogénes et de provenances diverses. Nous nous focalisons sur le problème de l'allocation des noeuds et présentons Salute, un service d'allocation de noeuds, qui organise les noeuds en réseaux virtuels non-structurés et repose sur des mécanismes de prédiction de disponibilité pour assurer, avec une grande probabilité, que les requêtes d'allocation sont satisfaites dans le temps, malgré le dynamisme de l'environnement hôte. Pour ce faire, le service Salute repose sur la collaboration de plusieurs protocoles pair-à-pair appartenant à la catégorie des protocoles épidémiques. Afin de valider nos propositions, nous évaluons Salute en utilisant des traces provenant d'un échantillonnage de plusieurs systèmes pair-à-pair de référenceWith the emergence of Cloud computing, a new trend is to externalize computing tasks in order to decrease costs and increase flexibility. Current Cloud infrastructures rely on the usage of large-scale centralized data centers, for computing resources provisioning. In this thesis, we study the possibility to provide a peer-to-peer based Cloud infrastructure, which is totally decentralized and can be deployed on any computing nodes federation. We focus on the nodes allocation problem and present Salute, a nodes allocation service that organizes nodes in unstructured overlay networks and relies on mechanisms to predict node availability in order to ensure, with high probability, that allocation requests will be satisfied over time, and this despite churn. Salute's implementation relies on the collaboration of several peer-to-peer protocols belonging to the category of epidemic protocols. To convey our claims, we evaluate Salute using real traces
42
Maurer, Alexandre. "Communication fiable dans les réseaux multi-sauts en présence de fautes byzantines." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066347/document.
Анотація:
A mesure que les réseaux s'étendent, ils deviennent de plus en plus susceptibles de défaillir. En effet, leurs nœuds peuvent être sujets à des attaques, pannes, corruptions de mémoire... Afin d'englober tous les types de fautes possibles, nous considérons le modèle le plus général possible : le modèle Byzantin, où les nœuds fautifs ont un comportement arbitraire (et donc, potentiellement malveillant). De telles fautes sont extrêmement dangereuses : un seul nœud Byzantin, s'il n'est pas neutralisé, peut déstabiliser l'intégralité du réseau.Nous considérons le problème d'échanger fiablement des informations dans un réseau multi-Sauts malgré la présence de telles fautes Byzantines. Des solutions existent mais nécessitent un réseau dense, avec un grand nombre de voisins par nœud. Dans cette thèse, nous proposons des solutions pour les réseaux faiblement connectés, tels que la grille, où chaque nœud a au plus 4 voisins. Dans une première partie, nous acceptons l'idée qu'une minorité de nœuds corrects échouent à communiquer fiablement. En contrepartie, nous proposons des solutions qui tolèrent un grand nombre de fautes Byzantines dans les réseaux faiblement connectés. Dans une seconde partie, nous proposons des algorithmes qui garantissent une communication fiable entre tous les nœuds corrects, pourvu que les nœuds Byzantins soient suffisamment distants. Enfin, nous généralisons des résultats existants à de nouveaux contextes : les réseaux dynamiques, et les réseaux de taille non-BornéeAs modern networks grow larger and larger, they become more likely to fail. Indeed, their nodes can be subject to attacks, failures, memory corruptions... In order to encompass all possible types of failures, we consider the most general model of failure: the Byzantine model, where the failing nodes have an arbitrary (and thus, potentially malicious) behavior. Such failures are extremely dangerous, as one single Byzantine node, if not neutralized, can potentially lie to the entire network. We consider the problem of reliably exchanging information in a multihop network despite such Byzantine failures. Solutions exist but require a dense network, where each node has a large number of neighbors. In this thesis, we propose solutions for sparse networks, such as the grid, where each node has at most 4 neighbors. In a first part, we accept that some correct nodes fail to communicate reliably. In exchange, we propose quantitative solutions that tolerate a large number of Byzantine failures, and significantly outperform previous solutions in sparse networks. In a second part, we propose algorithms that ensure reliable communication between all correct nodes, provided that the Byzantine nodes are sufficiently distant from each other. At last, we generalize existing results to new contexts: dynamic networks, and networks with an unbounded diameter
43
Nisse, Nicolas. "Complexité algorithmique: entre structure et connaissance. Comment les jeux de poursuite peuvent apporter des solutions." Habilitation à diriger des recherches, Université Nice Sophia Antipolis, 2014. http://tel.archives-ouvertes.fr/tel-00998854.
Анотація:
Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.
44
Tixeuil, Sébastien. "Vers l'auto-stabilisation des systèmes à grande échelle." Habilitation à diriger des recherches, Université Paris Sud - Paris XI, 2006. http://tel.archives-ouvertes.fr/tel-00124848.
45
Pelle, Robin. "Contribution à la modélisation formelle d'essaims de robots mobiles." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASG062.
Анотація:
L’algorithmique distribuée fait partie des domaines où le raisonnement informel n’est pas une option, en particulier lorsque des erreurs dites byzantines peuvent survenir. Elle est également caractérisée par une grande diversité de modèles dont les modulations subtiles impliquent des propriétés radicalement différentes. Nous nous intéressons aux « réseaux de robots » : nuages d’entités autonomes devant accomplir une tâche en coopération. Les applications que laissent envisager ces essaims d’agents sont extrêmement prometteuses : exploration et recherche de survivants dans des zones dévastées, patrouilles et vols de drones en formation, etc. Ces quelques exemples potentiellement critiques soulignent la grande dynamicité du modèle; ils indiquent également à quel point des défaillances des robots ou des erreurs dans les protocoles distribués qui les équipent peuvent avoir de désastreuses conséquences.Pour garantir la sûreté des protocoles et la sécurité des tâches, nous visons à l’obtention, à l’aide de l’assistant à la preuve Coq, de validations mécaniques formelles de propriétés de certains protocoles distribués.Un prototype de modèle formel Coq pour les réseaux de robots, Pactole, a récemment montré la faisabilité d’une approche de vérification par assistant à la preuve dans ce cadre. Il capture assez naturellement de nombreuses variantes de ces réseaux, notamment en ce qui concerne la topologie ou les propriétés des démons. Ce modèle est bien sûr à l’ordre supérieur et s’appuie sur des types coinductifs. Il permet de démontrer en Coq à la fois des propriétés positives : le programme embarqué permet de réaliser la tâche quelle que soit la configuration de départ, comme des propriétés négatives : il n’existe aucun programme embarqué permettant de réaliser la tâche.Dans le cadre émergent des réseaux de robots, les modèles sont distingués par les caractéristiques et capacités des robots, la topologie de l’espace dans lequel ils évoluent, le degré de synchronisme (modélisé par les propriétés du démon d’activation), les erreurs pouvant survenir, etc. Le prototype Pactolen’exprime que certaines de ces variantes. Pensé dans un cadre théorique (robots ponctuels, déplacements instantanés, etc.), des hypothèses restent hors de sa portée, en particulier des hypothèses réalistes comme des exécutions totalement asynchrones ou des risques de collision. L’absence de collision est fondamentale dans toutes les applications liées aux évolutions en formation (drones) et unecondition de sécurité critique dès qu’on s’intéresse au transport aérien. Une validation formelle de cette propriété revêt donc une grande importance.Le travail consiste à étendre le modèle formel afin de prendre en compte des évolutions asynchrones de robots volumineux. Cette modélisation doit permettre une formulation aisée de protocoles et des tâches qu’ils sont censés réaliser. On s’intéressera en particulier à garantir l’absence de collision au cours de déplacements potentiellement complexesDistributed Algorithm is among domains where informal reasoning is not an option, especially when Byzantine errors may occur. It is also characterized by a large variety of models whose subtle modulations imply radically different properties.We are interested in "robotic network": clouds of autonomous entities performing a cooperative task. The applications that these swarms of agents offer are extremely promising: exploration and search for survivors in devasted areas, patrols and drone flights in formation, etc. These few potentially critical exemples underline the high dynamicity of the model; they also indicate how failures of robots or errors in the distributed protocols that equip them can have distastrous consequences.To ensure the safety of the protocols and the security of tasks, we aim to optain, with the help of the Coq proof assistant, foraml mechanical validations of properties of certain distributed protocols. A prototype of Coq's formal model for robot network, Pactole, has recently shown the feasibility of an proof assistant verification in this framework. It captures quite naturally many variants of these networks, especially with regard to topology or the properties of demons. This model is of course in the higher order, and is based on coinductive types. It makes it possible to demonstrate in Coq both positive roperties: the embedded program makes it possible to carry out the task regardless of the initial configuration, as negative properties: there is no embedded program to complete the task.In the emerging framework of robot networks, the models are distinguished by the characteristics and capabilities of the robots, the topology of the space in which they evolve, the degree of synchronism (modelled by the properties of the activation demon), the error that can occure, etc. The prototype Pactole expresses only some of these variants. Thought in a theoretical framework (point robots, instantaneous movement, etc.), hypotheses remain out of reach, in particular realistic hypothesis such as totally asynchronous executions, or risk of collision. The absence of collision is fundamental in all applications relates to formation flights (drones) and critical safety condition as soon as one is interested in air transport. Formal validation of this property is therefore of great importance.The work consits of extending the formal model to take into account asynchronous evolutions of large robots. This modelling should allow easy formulation of protocols and the task they are supposed to perform. Particular attention will be given to ensuring the absence of collisions during potentially complex movements
46
Legaux, Joeffrey. "Squelettes algorithmiques pour la programmation et l'exécution efficaces de codes parallèles." Phd thesis, Université d'Orléans, 2013. http://tel.archives-ouvertes.fr/tel-00990852.
Анотація:
Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les pro- grammeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d'ordre supérieur synthétisant le comportement d'algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l'effort de programmation nécessaire sur OSL et d'autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d'utilisation tout en produisant des performances acceptables.
47
Filou, Vincent. "Une étude formelle de la théorie des calculs locaux à l'aide de l'assistant de preuve Coq." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14708/document.
Анотація:
L'objectif de cette thèse est de produire un environnement permettant de raisonner formellement sur la correction de systèmes de calculs locaux, ainsi que sur l'expressivité de ce modèle de calcul. Pour ce faire, nous utilisons l'assistant de preuve Coq. Notre première contribution est la formalisation en Coq de la sémantique des systèmes de réétiquetage localement engendrés, ou calculs locaux. Un système de calculs locaux est un système de réétiquetage de graphe dont la portée est limitée. Nous proposons donc tout d'abord une implantation succincte de la théorie des graphes en Coq, et utilisons cette dernière pour définir les systèmes de réétiquetage de graphes localement engendrés. Nous avons relevé, dans la définition usuelle des calculs locaux, certaines ambiguïtés. Nous proposons donc une nouvelle définition, et montrons formellement que celle-ci capture toutes les sous-classes d'algorithmes étudiées. Nous esquissons enfin une méthodologie de preuve des systèmes de calculs locaux en Coq.Notre seconde contribution consiste en l'étude formelle de l'expressivité des systèmes de calculs locaux. Nous formalisons un résultat de D. Angluin (repris par la suite par Y. Métivier et J. Chalopin): l'inexistence d'un algorithme d'élection universelle. Nous proposons ensuite deux lemmes originaux concernant les calculs locaux sur les arêtes (ou systèmes LC0), et utilisons ceux-ci pour produire des preuves formelles d'impossibilité pour plusieurs problèmes: calcul du degré de chaque sommet, calcul d'arbre recouvrant, etélection. Nous proposons informellement une nouvelles classes de graphe pour laquelle l'élection est irréalisable par des calculs locaux sur les arêtes.Nous étudions ensuite les transformations de systèmes de calculs locaux et de leur preuves. Nous adaptons le concept de Forward Simulation de N. Lynch aux systèmes de calculs locaux et utilisons ce dernier pour démontrer formellement l'inclusion de deux modes de détection de terminaison dans le cas des systèmes LC0. La preuve de cette inclusion estsimplifiée par l'utilisation de transformations "standards" de systèmes, pour lesquels des résultats génériques ont été démontrés. Finalement, nous réutilisons ces transformations standards pour étudier, en collaboration avec M. Tounsi, deux techniques de composition des systèmes de réétiquetage LC0. Une bibliothèque Coq d'environ 50000 lignes, contenant les preuves formelles des théorèmes présentés dans le mémoire de thèse à été produite en collaboration avec Pierre Castéran (dont environ 40%produit en propre par V. Filou) au cours de cette thèseThe goal of this work is to build a framework allowing the study, in aformal setting, of the correctness of local computations systems aswell as the expressivity of this model. A local computation system isa set of graph relabelling rules with limited scope, corresponding to a class of distributed algorithms.Our first contribution is the formalisation, in the Coq proofassistant, of a relationnal semantic for local computation systems.This work is based on an original formal graph theory for Coq.Ambiguities inherent to a "pen and paper" definition of local computations are corrected, and we prove that our definition captures all sub-classes of relabelling relations studied in the remainder. We propose a draft of a proof methodology for local computation systems in Coq. Our second contribution is the study of the expressivity of classes of local computations inside our framework. We provide,for instance, a formal proof of D. Angluin results on election and graph coverings. We propose original "meta-theorems" concerningthe LC0 class of local computation, and use these theorem to produce formal impossibility proofs.Finally we study possible transformations of local computation systemsand of their proofs. To this end, we adapt the notion of ForwardSimulation, originally formulated by N. Lynch, to localcomputations. We use this notion to define certified transformationsof LC0 systems. We show how those certified transformation can be useto study the expressivity of certain class of algorithm in ourframework. We define, as certified transformation, two notions ofcomposition for LC0 systems.A Coq library of ~ 50000 lines of code, containing the formal proofs of the theorems presented in the thesis has been produced in collaboration with Pierre Castéran
48
Fuguet, Tortolero César. "Introduction de mécanismes de tolérance aux pannes franches dans les architectures de processeur « many-core » à mémoire partagée cohérente." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066462/document.
Анотація:
L'augmentation continue de la puissance de calcul requise par les applications telles que la cryptographie, la simulation, ou le traitement du signal a fait évoluer la structure interne des processeurs vers des architectures massivement parallèles (dites « many-core »). Ces architectures peuvent contenir des centaines, voire des milliers de cœurs afin de fournir une puissance de calcul importante avec une consommation énergétique raisonnable. Néanmoins, l'importante densité de transistors fait que ces architectures sont très susceptibles aux pannes matérielles. L'augmentation dans la variabilité du processus de fabrication, et dans les facteurs de stress des transistors, dégrade à la fois le rendement de fabrication, et leur durée de vie. Nous proposons donc un mécanisme complet de tolérance aux pannes franches, permettant les architectures « many-core » à mémoire partagée cohérente de fonctionner dans un mode dégradé. Ce mécanisme s'appuie sur un logiciel embarqué et distribué dans des mémoires sur puce (« firmware »), qui est exécuté par les cœurs à chaque démarrage du processeur. Ce logiciel implémente plusieurs algorithmes distribués permettant de localiser les composants défaillants (cœurs, bancs mémoires, et routeurs des réseaux sur puce), de reconfigurer l'architecture matérielle, et de fournir une cartographie de l'infrastructure matérielle fonctionnelle au système d'exploitation. Le mécanisme supporte aussi bien des défauts de fabrication, que des pannes de vieillissement après que la puce est en service dans l'équipement. Notre proposition est évaluée en utilisant un prototype virtuel précis au cycle d'une architecture « many-core » existanteThe always increasing performance demands of applications such as cryptography, scientific simulation, network packets dispatching, signal processing or even general-purpose computing has made of many-core architectures a necessary trend in the processor design. These architectures can have hundreds or thousands of processor cores, so as to provide important computational throughputs with a reasonable power consumption. However, their important transistor density makes many-core architectures more prone to hardware failures. There is an augmentation in the fabrication process variability, and in the stress factors of transistors, which impacts both the manufacturing yield and lifetime. A potential solution to this problem is the introduction of fault-tolerance mechanisms allowing the processor to function in a degraded mode despite the presence of defective internal components. We propose a complete in-the-field reconfiguration-based permanent failure recovery mechanism for shared-memory many-core processors. This mechanism is based on a firmware (stored in distributed on-chip read-only memories) executed at each hardware reset by the internal processor cores without any external intervention. It consists in distributed software procedures, which locate the faulty components (cores, memory banks, and network-on-chip routers), reconfigure the hardware architecture, and provide a description of the functional hardware infrastructure to the operating system. Our proposal is evaluated using a cycle-accurate SystemC virtual prototype of an existing many-core architecture. We evaluate both its latency, and its silicon cost
49
Marchand, Corine. "Mise au point d'algorithmes répartis dans un environnement fortement variable, et expérimentation dans le contexte des pico-réseaux." Phd thesis, Grenoble INPG, 2004. http://tel.archives-ouvertes.fr/tel-00008039.
Анотація:
L'évolution technique des "objets communicants" tels que les ordinateurs portables, les assistants personnels, etc..., confirme l'intérêt porté aux technologies "sans fil". Le développement rapide des protocoles de communication sans fil (Bluetooth, WIFI, ...) a permis la généralisation de nouveaux "réseaux locaux ad-hoc" principalement caractérisés par leur topologie dynamique et l'hétérogénéité de leurs composants. Aussi, les infrastructures logicielles reposant sur de tels environnements doivent pouvoir s'adapter et gérer cette dynamicité (connexions/déconnexions fréquentes ainsi que la forte variabilité des communications. Dans ce contexte, l'objectif général est de concevoir des algorithmes permettant de maintenir la cohérence d'un groupe d'entités hétérogènes partageant des services sur des architectures fortement instables. La problématique concerne donc la prise de décision en environnement distribué en considérant les particularités du réseau sous-jacent. Dans cette thèse, nous proposons une méthodologie d'approche concernant la caractérisation des performances envisageables dans un environnement totalement distribué s'appuyant sur un protocole de communication sans fil. Cette approche consiste également en l'identification des différentes perturbations susceptibles d'interférer dans le bon déroulement des applications. Par ailleurs, un algorithme de consensus adapté aux spécificités de l'environnement et basé sur un principe d'interaction avec un mécanisme de détection de défaillances a été développé et implanté. Afin de valider cette approche algorithmique, diverses expérimentations et évaluations qualitatives et quantitatives ont été réalisées.
50
Saad, Clément. "Quelques contributions dans les réseaux de capteurs sans fil : Localisation et Routage." Phd thesis, Université d'Avignon, 2008. http://tel.archives-ouvertes.fr/tel-00364914.
Анотація:
Comme le firent Internet et les communications sans fil il y a de cela quelques décennies, l'avènement des réseaux de capteurs s'apprête à révolutionner notre mode de vie. Mais avant de voir ces réseaux atteindre un degré de démocratisation identique à celui des téléphones portables par exemple, un certain nombre de problématiques doit être résolu. Aux contraintes traditionnelles des réseaux ad hoc s'ajoutent les limites très strictes liées aux caractéristiques matérielles des capteurs telles que la puissance de calcul, la mémoire et surtout l'alimentation en énergie, rendant les algorithmes existants inadaptés. Cette thèse aborde deux problématiques : celle de la localisation et celle du routage. Concernant la localisation, une famille de trois méthodes est proposée pour estimer les positions des capteurs en y associant des bornes d'erreur, à partir de localisations exactes connues pour certains d'entre eux et en fonction de leurs capacités de mesures. Cette famille est ensuite étendue aux réseaux de capteurs mobiles. Vient alors le problème du routage permettant l'acheminement d'un message d'un capteur vers une station de base lorsqu'il détecte un événement. Les stratégies de routage dit géographique s'appuient sur les positions des capteurs qui sont considérées comme exactes. Or, dans la pratique, ces positions sont rarement précises. Cette thèse propose deux algorithmes de routage destinés respectivement aux réseaux de capteurs statiques et mobiles en considérant des positions estimées, rendant ainsi ces méthodes compatibles avec les algorithmes de localisation.