View
272
Download
2
Category
Preview:
Citation preview
1
Broadcast(diffusion, IP)
2
3
4
synchrone
5
6
7
complexité temps:
dprofondeur
n sommets
complexité en messages:
)(dO)(nO
8
asynchrone
9
10
11
12
13
14
complexité temps:
dprofondeur
n sommets
complexité nbre mesg:
)(dO)(nO
15
Convergecast(Rétroaction, Feedback, Echo)
•Chaque feuille de l’arbre envoie un accusé à son père
•chaque sommet interne achemine (à son tour) l’information vers son propre...
•jusqu’à la racine
•Application: PIF, terminaison, calcul max
16
synchrone
17
18
19
20
complexité temps:
dprofondeur
n sommets
complexité en nbre mesg:
)(dO)(nO
21
asynchrone
22
23
24
25
26
complexité temps:
dprofondeur
n
complexité en nbre mesg:
)(dO)(nO
sommets
27
Application au calcul d’un arbre recouvrant BFS
28
synchrone
29
30
31
32
33
34
35
36
37
reject
38
39
40
Autre solution
41
42
reject
43
44
45
complexité temps:
Ddiamètere
n sommets
complexité en nbre mesg:
)(DO)(mO
m arêtes
46
asynchrone
47
48
49
50
51
52
53
54
55
56
57
reject
58
59
60
reject
61
62
complexité temps:
Ddiamètere
n
complexité en nbre mesg:
)(DO)(mO
m arêtes
sommets
63
Building a DFS Spanning Tree
64
12
11
2
3
1
23
1
23
1
2
12
34
2
34
65
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
66
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
67
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
68
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
69
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
70
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
71
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1reject
72
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
73
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
74
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
75
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
76
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
reject
77
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
78
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
reject
79
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
80
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
81
complexité en temps:
n sommets
complexité en message:
)(mO)(mO
m arêtes 12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
82
Building a DFS Spanning Treewith no specified root
83
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
84
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
1
85
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
181
86
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
181
87
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
881
88
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
881
89
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
881
reject
90
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
1
8
881
91
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
8
8
881
92
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
8
8
881
8
93
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
8
8
881
8
8
94
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
8
8
881
8
8
95
12
11
2
3
1
23
1
23
1
2
12
34
2
34
8
8
8
8
881
8
8
96
12
11
2
3
1
23
1
23
1
2
12
34
2
34
8
8
8
8
881
8
8
97
12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
8
8
881
8
8
root
98
Time complexity:
n nodes
Message complexity:
)(mO)( mnO
m edges 12
11
2
3
1
23
1
23
1
2
12
34
2
34
1
8
8
8
881
8
8
root
Recommended