Sujet : Calcul distribué d'arbres couvrants de poids minimum

Responsable : Cyril Gavoille, Mohamed Mosbah
Téléphone : 05.40.00.88.12, 05.40.00.69.17
e-mail : gavoille@labri.fr, mosbah@labri.fr
Site Web : http://dept-info.labri.fr/~gavoille, http://www.labri.fr/visidia/
Equipe : L3A, Graphes & Applications

Présentation du sujet :

On considère un réseau de processeurs ayant une topologie quelconque. Il est
représenté par un graphe étiqueté, connexe, et non orienté, où les sommets
correspondent aux processeurs et les arêtes aux canaux de communication.
L'étiquette d'un sommet (resp. d'une arête) code l'état du processeur
(resp. du lien de communication) correspondant. Un calcul sur un réseau, qui
consiste donc à faire évoluer ces états, peut être décrit par des règles de
réécriture de graphes. Chaque règle, définie par un graphe connexe et deux
étiquetages de ce graphe, traduit une étape élémentaire du calcul effectuée
sur une portion locale du graphe. De nombreux algorithmes distribués
peuvent être exprimé dans ce modèle, on peut citer à titre d'exemples le calcul
distribué d'un arbre recouvrant, l'élection, la terminaison, ou encore l'exclusion
mutuelle distribuée. Toutefois, on ne peut pas exprimer des problèmes
d'optimisation.

Le but de cette thèse est d'étudier les algorithmes distribués qui calculent
des arbres recouvrants avec contrainte (poids minimal, poids maximal, degré minimal,
etc). Chaque processeur (sommet) met à jour des informations locales selon
les informations échangées avec ces voisins, afin d'optimiser le calcul global.
L'une des contributions attendues serait l'amélioration de complexité,
enétudiant éventuellement ce problème sur des classes de graphes particulières.


Mot-clés : Algorithmes distribués, systèmes distribués, routage

Références :
[1] S. Kutten and D. Peleg. Fast Distributed Construction of Small
k-Dominating Sets and Applications. In Journal of Algorithms,
28:40-66, 1998.