Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00075408
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 6:09:38 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 10:59:40 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

423

Files downloads

163