- Titre du sujet : Modélisations et étude de la puissance des systèmes

                    distribués  avec communication  par mémoires

 

 - Encadrant : Yves Métivier

 

 - Laboratoire et équipe de recherche : LaBRI - Combinatoire et algorithmique

 

 - Description détaillée.

 

   Ce travail s'inscrit dans le cadre général de

   l'algorithmique des systèmes distribués.

   Un système distribué est modélisé par un graphe : les sommets codent

   les processeurs ou les processus et une  arête code une communication

   directe entre deux sommets.

   Pour modéliser un algorithme dans un tel système, 3 paradigmes sont

   utilisés : calculs locaux, communications par messages et communications

   par mémoires.

   De nombreuses études ont été faites sur les 2 premiers et en particulier

   la caractérisation de leur puissance à travers des problèmes classiques

   comme le nommage, l'élection, le calcul d'un arbre recouvrant, la

   détection de la terminaison ou bien encore l'identification de propriétés

   topologiques du graphe sous jacent.

   Le travail proposé dans  cette thèse consiste principalement

   en l'étude de ces problèmes dans cadre des systèmes distribués avec

   communication  par mémoires. Il comporte en particulier

   les volets suivants :

 

     - formalisation des principaux modèles de communication par mémoire,

 

     - étude de ces modèles  à travers les problèmes donnés ci-dessus,

 

     - comparaison de la puissance de ces modèles avec les modèles des

       calculs locaux et le modèle où la communication se fait par messages.