Paola Flocchini 1

YO-YO
Élection dans les graphes arbitraires:
simple mais non-optimale
Paola Flocchini
Yo-Yo
DAG = graphe orienté acyclique
(Directed Acyclic Graph)
SOURCE:
PUITS:
NOEUD INTERNE:
Paola Flocchini
Paola Flocchini
1
Phase d'initialisation
Soit un graphe arbitraire non-orienté,
5
7
2
1
3
4
8
9
6
Paola Flocchini
Phase d'Initialisation
Soit un graphe arbitraire non orienté. Les liens sont dirigés des
petites entités vers les plus grandes (par des échanges de
messages entre voisins).
5
7
2
1
3
4
8
9
6
DAG
Paola Flocchini
Paola Flocchini
2
DAG
11
3
5
12
14
20
7
2
4
31
41
3
4
5
14
7
2
11
31
12
Puits
Source
20
Paola Flocchini
41
Le Protocole
3
4
5
3
3
4
7
5
2
7
2
YO: messages vers le bas
5
3
3
5
7
4 3
3
3
Y
Y
Y
N
4
N
N
N
5
N
N
7
N
2
Y
Y
Oui au minimum
Non aux autres
YO: messages vers le haut
Y
Y
Paola Flocchini
Paola Flocchini
3
Le Protocole
Oui au minimum
Non aux autres
NON
OUI
3
y
3
y
4
y
n
5
5
n
n
n
7
n
n
2
n
y
Paola Flocchini
Le Protocole
La direction des liens recevant NON sera inversé.
Les sources recevant au moins un NON deviendront
des puits ou des noeuds internes.
Paola Flocchini
Paola Flocchini
4
y
3
n
1. À chaque étape, au moins une
source deviendra un puits ou un
noeud interne.
y
y
y
4
n
3
y
y
n
n
Paola Flocchini
*
2. Un noeud interne ne peut pas devenir
une source après l'inversion du lien
*
3. Un puits ne peut pas devenir
une source après l'inversion du
lien
Par 1. 2. et 3.:
Le nombre de source est toujours
décroissant
Paola Flocchini
Paola Flocchini
5
3
Y
Y N
4
5
N
N
Y
N
N
7
N
N
2
Y
YO: messages vers le haut
Y
Y
Inversion
Y
3
2
Paola Flocchini
3
3
2
3
3
2
3
3
YO: messages vers le
bas
3
3
3
3
3
3
3
2
Paola Flocchini
Paola Flocchini
6
3
Y
2
N
N
Y
N
Y
YO: messages vers le
haut
Y
N
Y
Y
Y
Y
N
Y
Paola Flocchini
2
Inversion
Paola Flocchini
Paola Flocchini
7
Terminaison
?
ÉLAGAGE
(pruning)
Paola Flocchini
Règles d'Élagage (pruning)
1)
2)
Les puits ayant seulement un
lien entrant peuvent être
éliminés
(La décision du puits sera la
même que celle du parent)
x x x
x x x
Paola Flocchini
Paola Flocchini
Les noeuds qui reçoivent plusieurs
valeurs identiques:
Parmis tous les liens ayant une
valeur identique, un seul doit être
préservé
(Ils viennent de la même source, la
décision sera donc la même)
8
3
4
3
4
5
5
3
7
2
7
2
5
3
3
4 3
YO – messages vers le bas
5
7
3
3
4
Y N
N
N
Y
N
5
N
N
7
N
2
Y
Y
YO – messages vers le
haut + information
d'élagage
Y(prune me….)
Y
Y(prune me….)
Paola Flocchini
En même temps …. élagage
3
4
Y N
N
N
Y
N
5
N
N
7
N
2
Y
Y
Y
Paola Flocchini
Paola Flocchini
9
3
2
INVERSION
3
2
Paola Flocchini
3
3
2
3
2
3
3
3
3
2
3
3
3
3
3
YO: messages vers le
bas
Paola Flocchini
Paola Flocchini
10
Y
3
2
Y
Y
N
Y (prune me)
Y (prune me)
Y(prune me)
Y
N
Y
Y(prune me) N
YO: messages
vers le haut
Y
Paola Flocchini
3
2
3
En même temps …. élagage
3
3
2
3
2
3
3
3
Paola Flocchini
Paola Flocchini
3
3
3
3
2
3
11
3
2
… élagage
Paola Flocchini
3
2
Paola Flocchini
Paola Flocchini
12
2
INVERSION
Paola Flocchini
2
2
2
YO: messages vers
le bas
2
2
2
Paola Flocchini
Paola Flocchini
13
2
2
2
Élagage
2
2
2
Paola Flocchini
2
2
Élagage
2
2
2
Paola Flocchini
Paola Flocchini
14
2
2
Élagage
2
2
Paola Flocchini
2
2
Élagage
2
Paola Flocchini
Paola Flocchini
15
2
2
Élagage
Paola Flocchini
2
Élagage
Paola Flocchini
Paola Flocchini
16
Complexité
Sans Élagage
Il y aura 2 messages pour chaque lien à chaque
phase.
- Le nombre de phases est: log(s)
(s = # sources)
TOT: m + 2m log s
Avec Élagage:
?
Pour initialisation
Paola Flocchini
Construction d'un Arbre Recouvrant et Élection
n: nombre de noeuds
m: nombre de liens
Arbre Recouvrant + O(n) ---> Élection
Élection + O(m) ---> Arbre Recouvrant
a) Élection ≤ Arbre Recouvrant + O(n)
b) Arbre Recouvrant ≤ Élection + O(m)
Élection = Ω(m + n log n)
Arbre Recouvrant = Ω(m + n log n)
Paola Flocchini
Paola Flocchini
17

Download Report