Élection Autostabilisante dans les Réseaux à Haute Dynamicité
2020
Nous nous interessons a la conception d'algorithmes autostabilisants pour des reseaux identifies hautement dynamiques. Precisement, nous considerons le probleme de l'election dans trois classes de graphes dynamiques (TVG) : la classe T C B (∆) des TVG de diametre temporel borne par ∆, la classe TCQ (∆) des TVG de diametre temporel quasiment borne par ∆ et la classe TCR des TVG a connectivite temporelle recurrente. Nous montrons qu'en depit des identites, dans les classes TCQ (∆) et TCR, tout algorithme autostabilisant d'election necessite la connaissance exacte du nombre de processus. Puis nous proposons trois algorithmes d'election. Le premier, pour la classe TCB(∆), stabilise en au plus 3∆ rondes. Dans TCQ(∆) et TCR, le temps de stabilisation d'un algorithme autostabilisant d'election ne peut pas etre borne. Cependant, nous montrons que nos deux solutions sont speculatives, c'est-a-dire qu'elles ont de bonnes performances dans des cas favorables ; en effet, elles stabilisent en O(∆) rondes lorsque l'on se restreint a la classe TCB(∆).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI