- 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.