Abstract FR:

La premiere partie de cette these est consacree a l'etude du degre de parallelisme des monoides de commutation modelisant les executions distribuees des algorithmes. Apres une presentation du modele et des differents resultats deja etablis, nous donnons des methodes pour calculer ce degre, l'outil principal utilise etant les marches aleatoires et les chaines de markov. La deuxieme partie s'interesse au probleme des synchronisations dans les reseaux anonymes. Des travaux ulterieurs ont montre que sous quelques hypotheses, on ne peut resoudre ce probleme de maniere deterministe, nous proposons donc et analysons des algorithmes probabilistes resolvant ce probleme, nous etudions egalement leur efficacite. La troisieme partie est consacree a l'etude d'un algorithme d'election dans un reseau en arbre ou dans tout reseau ou un arbre couvrant est disponible. Nous montrons que sous quelques hypotheses, le(s) sommet(s) median(a) a (ont) la probabilite la plus elevee d'etre elu(s), et nous donnons quelques implementations possibles de cet algorithme. Dans la derniere partie, nous nous interessons a l'etude de la taille memoire necessaire pour coder les tables de routage adaptatives dans un reseau de processeurs. Les principaux resultats de cette partie concernent la compacite de ces tables. En effet, nous montrons que tout reseau supporte un routage par intervalle -adaptatif de compacite 1. Si on impose au moins un plus court chemin, nous donnons une borne inferieure pour la compacite et, enfin, nous montrons que la difference entre la compacite dans le cas deterministe et la compacite dans le cas adaptatif peut etre tres grande.