Les réseaux d'interconnexion et les algorithmes distribués
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis contains two parts. Ln the first one we study interconnection networks and in particular their fault tolerance. The first chapter deals with the extensions of networks. We construct networks with given connectivity and maximum degree by adding the vertices p by p. In such a way that the minimum number possible of links is deleted. Ln chapter 2 we study the vulnerability of bus networks; this leads us to study various notions of connectivity in uniform hypergraphs. The second part concerns distributed algorithms, in particular problems of broadcasting and routing. Chapter 3 deals with the problem of broadcasting information or requests in a distributed net work. We give a new algorithm to construct a spanning tree and apply it to the problem of mutual exclusion. We use methods of control knowledge transfers and also synchronization and filtering methods. Ln chapter 4 we present a "meta-algorithm" based on the notion of phases. Furthermore we specify the use and the importance of the network topology in the distributed computing. Ln these two chapters we determine the complexity in number or messages and time of the proposed algorithms. Finally we give in the appendix a scheduling algorithm for parallel computing which is optimal for the 2-sceps precedence graph (Gaussian elimination in dense matrices).
Abstract FR:
Cette thèse comprend deux parties. La première concerne les réseaux d'interconnexion et en particulier leur résistance aux pannes. Le premier chapitre traite d'extension de réseaux; on construit des réseaux de connexité et de degré maximum donnés en ajoutant des sommets p par p par p ceci avec un nombre minimum de remaillages. Dans le second chapitre on étudie la vulnérabilité des réseaux par bus ce qui nous conduit à étudier diverses notions de connexité dans les hypergraphes uniformes. La deuxième partie est consacrée à l'algorithme, distribuée et particulièrement à tout ce qui concerne les problèmes de messagerie (diffusion, routage). Le chapitre 3 traite de la diffusion d'information ou de requêtes dans un réseau distribué. On définit un nouvel algorithme : permettant de construire un arbre couvrant et on l'applique au problème de l'on mutuelle. Nous utilisons des méthodes de contrôle des transferts de connaissance ainsi que des techniques de synchronisation et de filtrage. Le chapitre 4 présente un «méta-algorithme» distribué basé sur la notion de phases. De plus on précise le rôle et l’importance de la topologie du réseau dans l'algorithmique distribuée. Dans ces deux derniers chapitres on détermine la complexité en nombre de messages et en temps des algorithmes. Enfin nous donnons en annexe un algorithme d'ordonnancement pour le calcul parallèle qui est optimal si le graphe de précédence des tâches est de type "2-steps' (élimination de Gauss dans une matrice dense).