Un algorithme probabiliste d'election et d'arbre couvrant sur des reseaux anonymes

Résumé : Dans le present rapport, nous proposons deux variantes d'un algorithme distribue, probabiliste, asynchrone d'election et de construction d'arbre couvrant dans des reseaux anonymes a topologie quelconque. A notre connaissance, cet algorithme est le premier du genre, a etre totalement et rigoureusement specifie. Il est fonde sur un precedent algorithme deterministe d'election pour reseaux de processus a identites distinctes. Nous montrons ici comment construire les deux variantes, suivant deux contextes differents. Premierement- , nous considerons le cas ou on ne possede strictement aucune connaissance globale sur le reseau, ce qui conduit a un algorithme dans lequel on n'opere qu'un nombre limite, fixe d'avance, de tirages aleatoires. Il n'y a pas alors de moyen deterministe d'obtenir une "bonne" terminaison distribuee, et l'election comme la construction d'un arbre couvrant sont realises avec une probabilite ³ 1 - e, pour e > 0 donne. Et deuxiemement, en supposant qu'un processus au moins connaisse n le nombre total de processus du systeme, le probleme de l'election et de l'arbre couvrant sont resolus avec une terminaison correcte de l'algorithme, sans erreur. La terminaison correcte de l'algorithme tient ici au fait que l'un des processus finit par apprendre qu'il appartient a un arbre a n sommets, cet arbre est alors bien un arbre couvrant du reseau.
Type de document :
Rapport
RR-1151, INRIA. 1989
Liste complète des métadonnées

https://hal.inria.fr/inria-00075408
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:09:38
Dernière modification le : vendredi 16 septembre 2016 - 15:11:37
Document(s) archivé(s) le : mardi 12 avril 2011 - 22:59:40

Fichiers

Identifiants

  • HAL Id : inria-00075408, version 1

Collections

Citation

Ivan Lavallee, C. Lavault. Un algorithme probabiliste d'election et d'arbre couvrant sur des reseaux anonymes. RR-1151, INRIA. 1989. 〈inria-00075408〉

Partager

Métriques

Consultations de la notice

364

Téléchargements de fichiers

135