Algorithmes

distribués de base
Nabil Abdennadher

[Link]@[Link]

Infrastructure

2
 Plan
• Hypothèses de travail
• Généralités
• Collecte (Convergecast)
• Diffusion (Broadcast)
• Construction d’arbres de recouvrement
• Identification des noeuds d’un réseau
• Calcul du plus court chemin
• Algorithme d’élection
• Algorithmes de recherche

Hypothèses de travail

• Le système distribué est représenté par un graphe où les

nœuds sont les processeurs (ou devices) et les arêtes
sont les liens inter-noeuds : Gp = (Np, Ep)
• Les arêtes sont bi-directionnelles.
• La communication est basée sur la transmission de
messages (en ce qui concerne les alg. distribués qui
seront vus en cours)
• Un message est représenté par le couple (q, Msg)
• Msg doit être délivré au noeud q
• Msg : (u, msg) où u est la tâche exécutée par le noeud q et msg
est le message à délivrer à la tâche u

4
 Hypothèses de travail: Routage

• Au niveau de chaque nœud r, il existe une fonction

appelée nextr(q)
• prochain nœud à qui envoyer le message (sachant que nous
sommes au niveau du nœud r) pour atteindre q
• (r, nextr(q)) appartient à Ep.
• Cette fonction peut être fixe ou dynamique
• Elle peut être déterministe (nextr(q) est unique) ou non
• On supposera dans ce cours que la propriété FIFO est
vérifiée
• Au niveau d’un lien
• Au niveau de l’arrivée des messages au nœud destination

Hypothèses de travail: Flux de contrôle

• Cette fonction concerne le stockage des données en

transit et la gestion des ressources de communication
(liens, buffers)

• Les types de flux de contrôle les plus connus

• Store and forward
• Circuit switching
• Wormhole routing

• On supposera dans ce cours que le flux de contrôle

utilisé garantit l’absence de deadlock

6
 Flux de contrôle: Store and forward

• (q, Msg) est décomposé en plusieurs packets

• Les packets contiennent les même informations de
routage que le message lui même
• Les paquets sont transmis en parallèle
• Pour garantir le « FIFO », les packets sont numérotés
• Possibilité de deadlock: taille limitée des buffers

Flux de contrôle: Circuit switching

• Le chemin est réservé avant le début du transfert

• Possibilité de deadlock: un lien peut faire partie de
plusieurs chemins
• Pas efficace pour les petits messages

8
 Flux de contrôle: flow control (wormhole
routing)

• Les packets sont décomposés en flit (flow-control-digit)

• Le flit leader trace le chemin qui sera suivi par les autres
flits
• Seul le flit leader contient les informations de routage
• Contrairement à la méthode store-and-forward, la
transmission des packets est pipelinée

Plan
! Hypothèses de travail
! Généralités
! Collecte (Convergecast)
! Diffusion (Broadcast)
! Construction d’arbres de recouvrement
! Identification des noeuds d’un réseau
! Calcul du plus court chemin
! Algorithme d’élection
! Algorithmes de recherche

10
 Objectifs

• Etude théorique des algorithmes distribués de

bases
• Complexité : exprimée en terme de messages
transmis

11

Généralités

• L’application est représentée par un graphe orienté

GT= (NT, DT).
• Pour chaque tâche t:
• Intt : les liens entrant dans t. Intt appartient à DT
• Outt : les liens sortant de t. Outt appartient à DT
• Une tâche t est réactive (message driven)
• Elle effectue un traitement en réponse à un message reçu.
• Dans certains cas :
• Une ou plusieurs tâches initialisent le traitement de l’application
• Une tâche peut procéder à une étape d’initialisation

12
 Template d’un algorithme distribué

• Task_t
• Faire un traitement d’intialisation
• Envoyer un message à un sous ensemble de Outt (peut
être l’ensemble vide)
• Répéter
• A la réception d’un message sur un canal c1 (de intt) et Cond1 "
• Faire un traitement
• Envoyer un message à un sous ensemble de Outt
• ou …
• A la réception d’un message sur un canal cn (de intt) et Condn "
• Faire un traitement
• Envoyer un message à un sous ensemble de Outt
• Jusqu’à (une condition de fin)

13

Remarques …

• Condition d’arrêt
• La tâche est capable de « détecter » la condition d’arrêt à partir des
messages qu’elle reçoit
• La condition d’arrêt suppose aussi que la tâche ne reçoit plus de
messages
• guard " command
• La commande est exécutée lorsque « guard » est prêt: message
reçu et condition booléenne Condi vérifiée
• Un seul « guard » est exécuté à chaque itération
• En cas de présence de plusieurs « guard », un est sélectionné au
hasard
• En cas d’absence de « guard », la tâche ne fait rien

14
 Encore des remarques …

• Envoi et réception de messages

• L’envoi est non bloquant
• La réception est bloquante
• Ce schéma évite les «deadlocks»
• Les canaux (liens entre les tâches) délivrent les messages
dans un ordre FIFO
• Cette condition n’est pas nécessaires pour les
algorithmes qui seront étudiés

15

Plan
! Hypothèses de travail
! Généralités
! Collecte (Convergecast)
! Diffusion (Broadcast)
! Construction d’arbres de recouvrement
! Identification des noeuds d’un réseau
! Calcul du plus court chemin
! Algorithme d’élection
! Algorithmes de recherche

16
 Qu’est ce qu’un convergecast ?

• Tous les noeuds envoient une donnée locale à un

même noeud destinataire
• Au départ :
• Chaque noeud ni dispose d’une donnée locale Di
• A la fin :
• Toutes les données Di sont reçues par un noeud destinataire nr .

17

Structure de données : Arbre de

recouvrement

• Le réseau est modélisé par une structure appelée

arbre de recouvrement (Spanning Tree)
• AR est connu
• Au niveau de chaque nœud : le père + les fils
• Représentation distribuée
• Pourquoi ?
• Un arbre est plus facile à parcourir qu’un graphe

18
 Exemple d’arbre de recouvrement

Racine

• Le AR est représenté de manière

distribuée :
• Chaque noeud ni connaît :
• son père (NULL pour la racine)
• ses fils (NULL pour les feuilles)

19

Convergecast : Exemple
nr nr

n4
D5 D6

n6
D1 n5
Liens du AR
D3
D2 Liens non AR
n1 n1
Le noeud a reçu tous
n2 n3 les messages n2 n3
Le noeud n’a pas encore
reçu tous les messages

20
 Convergecast : Algorithme

• Chaque noeud feuille

• Envoie la donnée locale Di au noeud père
• Chaque noeud non feuille ni (i ≠ r)
• A la réception des messages de tous les noeuds fils
• Envoie l’ensemble des messages reçus au noeud père
• noeud nr
• Reçoit les messages de la part de tous les noeuds fils

21

Convergecast : Complexité

• n – 1 messages
• n opérations

22
 Plan

• Hypothèses de travail
• Généralités
• Collecte (Convergecast)
• Diffusion (Broadcast)
• Construction d’arbres de recouvrement
• Identification des noeuds d’un réseau
• Calcul du plus court chemin
• Algorithme d’élection
• Algorithmes de recherche
23

Qu’est ce qu’un braodcast ?

• Un (ou plusieurs) noeuds envoie une donnée

D à tous les noeuds du réseau
• Initialement :
• D se trouve sur un (ou plusieurs) noeuds :
Ensemble N0
• A la fin :
• D se trouve sur tous les noeuds du réseau.

24
 Broadcast avec arbre de
recouvrement : Exemple

nr nr
D D D D

Liens du AR
Liens non AR

noeud racine

noeud non racine

25

Broadcast avec arbre de

recouvrement : Algorithme

• Nœud racine nr
• Envoie la donnée D à tous les fils (arbre AR)

• Noeuds ni (i ≠ r)
• A la réception de la donnée D de la part du père
• Si ni n’est pas un nœud feuille
• Envoyer D à tous les fils de ni

26
 Broadcast avec arbre de
recouvrement : Complexité

• Chaque noeud :
• Reçoit un message de son père (sauf la racine)
• Envoie un message à ses fils (arbre AR)

• Nombre de messages : n – 1 messages

• Nombre d’opérations : n
• … mais il faut construire le AR auparavant
• Lorsque |N0| > 1, on peut utiliser plusieurs AR : Spanning
Forest.

27

Broadcast par vagues (Inondation)

D
noeuds possédant D
noeud ne possédant pas D

• Chaque noeud ni gère :

• Liste des voisins directs : vi
D
• Un booléen atteinti
• initialisé à faux
• mis à vrai si :
• ni appartient à N0
• ni reçoit D pour la 1ère fois

28
 Première vague : générée par N0

29

Broadcast par vagues : Algorithme

• atteinti = faux;

• Si ni appartient à N0
• atteinti = vrai
• Envoyer D à tous les voisins directs (vi)

• A chaque réception de D (* |vi| réceptions *)

• Si atteinti =faux (* 1ère réception de D *)
• atteinti := vrai
• Envoyer D à tous les voisins directs de ni

30
 Broadcast par vagues : Complexité

• La propagation de D se fait par vagues (waves)

• ni envoie une seul fois D à ses voisins directs
• ni reçoit D autant de fois qu’il a de voisins.
• Chaque lien du réseau transmet la donnée D
deux fois : Une fois dans chaque direction
• Complexité
• 2m messages (m : nombre de liens dans le
réseau)
• n “opérations” (n : nombre de noeuds)

31

Broadcast par vagues avec accusé de

réception: Principe

32
 Broadcast par vagues avec
accusé de réception

• L’ensemble N0 est un singleton

• Chaque nœud :
• est adopté par le 1er nœud qui lui envoie D
• Envoie D à tous ses voisins directs, sauf son père
• Recoit D autant de fois qu’il a de voisins directs
• A la réception du dernier D, envoie D à son père

33

Broadcast par vagues avec accusé de

réception

• Chaque noeud ni gère :

• Une liste des voisins directs : vi
• Un booléen atteinti initialisé à faux
• Un compteur counti initialisé à 0
• parenti initialisé à NULL

34
 Broadcast par vagues avec accusé de
réception : Algorithme

• Si ni appartient à N0 (ni est le noeud racine)

• atteinti := vrai
• Envoyer D à tous les voisins directs

(* Le reste est exécuté quelque soit le noeud *)

• A chaque réception D de la part d’un noeud nj (*|vi|
mesg*)
• counti = counti + 1;
• Si atteinti =faux
• atteinti := vrai
• parenti := nj
• Envoyer D à tous les voisins directs de ni ≠ nj
• Si counti = |vi| et parenti ≠ NULL
35
• Envoyer D à parenti

Broadcast par vagues avec

accusé de réception: Complexité

• Le noeud root nr envoie |vr| messages

• Chaque noeud ni ≠ nr
• Envoie |vi| - 1 messages
• Envoie un accusé de réception (D) à son père

• Nombre de messages : 2m
• 2m – n + 1
• En plus de l’accusé de réception : n – 1 (nombre de
liens dans l’arbre construit)
• Nombre “d’opérations” : n

36
 Broadcast par vagues avec ou sans
accusé de réception : Non déterminisme

Exécution 2

Exécution 1

37

Les algorithmes Broadcast en bref

• Par vagues (ou inondation)
• Asynchrone
• 2m messages
☺" • Avantage : Les liens utilisés varient d’une exécution à l’autre
• Par vague avec accusé de réception
• Synchrone
• 2m messages
☺" • Avantages
• Les liens utilisés varient d’une exécution à l’autre
• Construction de l’arbre de recouvrement
• En utilisant un arbre de recouvrement
• n – 1 messages
#" • Inconvénient
• Les mêmes liens inter-nœuds sont toujours utilisés
• Non tolérance aux pannes

38
 Plan
• Hypothèses de travail
• Généralités
• Collecte (Convergecast)
• Diffusion (Broadcast)
• Construction d’arbres de recouvrement
• Identification des noeuds d’un réseau
• Calcul du plus court chemin
• Algorithme d’élection
• Algorithmes de recherche

39

Trois algorithmes

• Construction d’un AR en largeur d’abord (Bredth First

Serach : BFS) avec racine identifiée
• Construction d’un AR en profondeur d’abord (Depth First
Search : DFS) avec racine identifiée
• Construction d’un AR sans racine identifiée

40
 Exemple
nr
M : Demande d’adoption R
nr P : Salut papa
M P R : Non ! Tu n’es pas papa
M M P
P
M M
M M
M

Liens du AR
Liens non AR

Le noeud a reçu
le message M
Le noeud n’a pas
encore reçu M

41

Structure de données

• Pour chaque noeud ni

• parent : parent du nœud ni. Initialisé à NULL
• F : Ensemble des fils de ni. Initialisé à NULL
• NF : Ensemble des Non Fils de ni. Initialisé à NULL
• v : Ensemble des voisins de ni

42
 Les messages

• Trois types de messages :

• M : Demande d’adoption d’un fils
• P : Tu as demandé mon adoption, tu es mon papa
• R : Tu as demandé mon adoption, merci mais j’ai déjà
un papa.

43

Algorithme (exécuté par nr)

• Pour le noeud racine nr

• Envoi d’un message <M> à tous les voisins
• Attente de messages <M>, <P> ou <R>
• A la réception d’un message <M>
• Envoyer un message <R>
• A la réception d’un message <P>
• Actualiser la liste des noeuds fils : F
• A la réception d’un message <R>
• Actualiser la liste des noeuds non fils : NF

44
 Algorithme (exécuté par ni , i ≠ r)

• Répéter
• A la première réception de M de la part de nj
• ni envoie un message <P> à nj
• parent = nj
• ni envoie un message <M> à tous les voisins autres que nj
• Pour les autres messages <M> reçus
• ni envoie le message <R> à l’émetteur
• Pour un message <P> reçu
• Actualiser la liste des processus fils : F
•?
• Pour un message <R> reçu
• Actualiser la liste des processus non fils : NF
• Jusquà (condition d’arrêt)
45

Test d’arrêt

• Un noeud non racine s’arrête d’attendre des

messages lorsque :
• |NF| + |F| + 1 = nombre de voisins

pére

Nombre de messages <R> Nombre de messages <P>

• Le noeud racine s’arrête d’attendre des messages

lorsque :
# |NF| + |F| = nombre de voisins

46
 Remarques

• L’algorithme BFS est écrit de sorte à privilégier un

parcours parallèle des voisins.
• L’AR généré est en général large avec peu de niveaux
• Est si on désire obtenir un AR étroit avec beaucoup de
niveaux ?

47

Trois algorithmes

• Construction d’un AR en largeur d’abord (Breadth First

Search : BFS) avec racine identifiée
• Construction d’un AR en profondeur d’abord (Depth First
Search : DFS) avec racine identifiée
• Construction d’un AR sans racine identifiée

48
 Structure de données

• Pour chaque noeud ni

• parent : parent du nœud ni. Initialisé à NULL
• F : Ensemble des fils de ni. Initialisé à NULL
• NF : Ensemble des Non Fils de ni. Initialisé à NULL
• v : Ensemble des voisins de ni
• NE : Ensemble des voisins de ni non encore
explorés. Initialement NE = v

49

Algorithme

• Pour le noeud racine nr

• parent = nr
• Choisir un nœud nk et l’enlever de NE
• Envoi <M> à nk

50
 Algorithme … suite
• Au niveau d’un noeud ni
• A la réception de <M> de la part de nj
• si parent = NULL /* Premier Message M reçu */
• parent = nj
• Enlever le nœud nj de NE
• si NE ≠ NULL
• Choisir un nœud nk et l’enlever de NE
• Envoi <M> à nk
• sinon /* Le Message M reçu n’est pas le premier */
• ni envoie le message <R> à l’émetteur
• A la réception de <P> ou <R> de la part de nj
• si le message reçu est <R> alors ajouter nj à NF
• si le message reçu est <P> alors ajouter nj à F
• si NEi ≠ NULL
• Choisir un nœud nk et l’enlever de NE
• Envoyer <M> à nk
51

Test d’arrêt

• Le noeud racine s’arrête d’attendre des messages lorsque :

• |NF| + |F| = nombre de voisins

• Un noeud non racine s’arrête d’attendre des messages

lorsque :
• |NF| + |F| + 1 = nombre de voisins
• En plus, Si parent ≠ ni (nœud non racine) alors envoyer un
message <P> à parent /* fin du programme */

52
 Trois algorithmes

! Construction d’un AR en largeur d’abord (Breadth First

Search : BFS) avec racine identifiée
! Construction d’un AR en profondeur d’abord (Depth First
Search : DFS) avec racine identifiée
! Construction d’un AR sans racine identifiée

53

Construction d’un AR, racine non

identifiée

• Chaque nœud ni est identifié par un identificateur idi

• Chaque nœud candidat tente de construire un AR de type DFS
en envoyant son propre id.
• Si deux arbres AR essaient de s’approprier un nœud, celui-ci est
affecté au AR ayant la plus grande racine.
• Chaque nœud gère une variable leader : le plus grand id reçu.
• Lorsqu’un nœud ni reçoit un message id de la part de nj
• si (id > leader)
• ni change de AR et envoie id à ses voisins (≠ nj)
• Si (id < leader)
• ni bloque le message
• Si (id = leader) // ni et nj appartiennent au même AR ayant la racine
leader
• ni envoie un message <R> à nj
54
 Structure de données

• Pour chaque noeud ni

• id : identifiant du nœud ni
• parent : parent du nœud ni. Initialisé à NULL
• leader : Plus grand id reçu par ni
• F : Ensemble des fils de ni. Initialisé à NULL
• NF : Ensemble des Non Fils de ni. Initialisé à NULL
• v : Ensemble des voisins de ni
• NE : Ensemble des voisins de ni non encore
explorés. Initialement NE = v
• terminé : booléen qui arrête l’algorithme au niveau
du nœud racine. Initialisé à faux.
55

Algorithme

• Pour tous les noeuds

• parent = NULL;
• leader = 0;
• F = NULL;
• NE = v;
• terminé = faux

• Chaque nœud ni candidat

• parent = ni
• leader = idi
• Choisir un nœud nk et l’enlever de NE
• Envoi <leader> à nk

56
 Algorithme … suite (au niveau de ni)

• A la réception de <y> de la part de nj

• si leader < y /* Passage à un autre arbre AR */
• leader = y; parent = nj ; NE = v - nj.
• si NE ≠ NULL /* Tous les voisins ne sont pas explorés */
• Choisir un nœud nk , l’enlever de NE et envoyer <leader> à nk
• Sinon ni envoie un message <P> à parent
• sinon /* leader >= y */
• si leader = y alors envoi du message <R> à l’émetteur nj /* ni déjà dans
l’arbre */
• A la réception de <P> ou <R> de la part de nj
• si le message reçu est <R> alors ajouter nj à NF
• si le message reçu est <P> alors ajouter nj à F
• si NEi = NULL
• si (parent ≠ ni) {envoyer <P> à parent; terminé = vrai} fsi
• sinon
• Choisir un nœud nk , l’enlever de NE et envoyer <leader> à nk
57

Test d’arrêt

• Un noeud non racine s’arrête d’attendre des messages

lorsque :
• |NF| + |F| + 1 = nombre de voisins

père

Nombre de <R> Nombre de <P>

# Le noeud racine s’arrête lorsque terminé est à vrai

58
 Plan

! Hypothèses de travail
! Généralités
! Collecte (Convergecast)
! Diffusion (Broadcast)
! Construction d’arbres de recouvrement
! Identification des noeuds d’un réseau
! Calcul du plus court chemin
! Algorithme d’élection
! Algorithmes de recherche
59

Problématique

• Objectif
• Disposer d’une vue du réseau au niveau de chaque
nœud
• Chaque nœud s’identifie aux autres :
• Type, Processeur, OS, performance, ressources, etc.
• Pourquoi ?
• Tolérance aux pannes : panne de certains nœuds du
réseau
• Gérer la qualité de service (Quality of Service)
• Choix du meilleur nœud pour un service donné

60
 Solutions

• 1ère solution
• Exécuter séquentiellement l’algorithme Broadcast avec
ACK n fois
• Chaque nœud envoie son identification aux autres
• 2ème solution
• Exécuter en parallèle l’algorithme Broadcast avec ACK:
Algorithme Test_Connectivity (TC)

61

Algorithme TC : Principe

• Algorithme Test_Connectivity
• Exécution en parallèle de l’algorithme Broadcast avec
accusé de réception
• Génération de n arbres de recouvrement (AR)
• Chaque nœud envoie son identificateur id à tous ses
voisins
• Les voisins propagent l’id reçu vers tous les nœuds
voisins (sauf le nœud émetteur)

62
 Algorithme TC

63

Algorithme TC : Structure de
données

• idi : Identifiant du nœud ni

• vi : liste des voisins directs
• atteinti (j)
• Booléen initialisé à faux et mis à vrai lors de la première
réception de idj par le nœud ni
• counti (j) : nombre de réception du message idj par le nœud ni
• parenti (j) :
• Initialisé à NULL.
• Pointe sur le nœud nk de vi qui a envoyé, pour la première fois, le
message idj à ni
• initi : booléen positionné à vrai si :
• ni appartient à N0 ou
• lors de la réception du premier message par ni

64
 Algorithme TC

• ni appartient à N0
• initi := vrai;
• atteinti (i) := vrai;
• Envoyer idi à tous les nœuds de vi

65

Algorithme TC … Suite

• Répéter
• A la réception de idk de la part de nj
• si non (initi) // ni envoie ses informations
• initi := vrai; atteinti (i) := vrai;
• Envoyer idi à tous les nœuds de vi
• counti (k) := counti (k) + 1;
• si non (atteinti (k))
• atteinti (k) := vrai
• parenti (k) := nj
• Envoyer idk à tous les voisins directs de ni ≠ nj
• si (counti (k) = |vi|) et (parenti (k) ≠ NULL)
• Envoyer idk à parenti (k)

• Jusqu’à (condition d’arrêt)

66
 Algorithme TC : Complexité

• n exécution de l’algorithme broadcast avec ACK

• 2 n*m messages
• n2 exécutions de l’algorithme broadcast avec ACK

67

Plan

! Hypothèses de travail
! Généralités
! Collecte (Convergecast)
! Diffusion (Broadcast)
! Construction d’arbres de recouvrement
! Identification des noeuds d’un réseau
! Calcul du plus court chemin
! Algorithme d’élection
! Algorithmes de recherche
68
 Calcul des plus courts chemins :
Calcul_PCC

• Quoi ? : Calcule le plus court chemin entre deux nœuds quelconque

du réseau.
• Pourquoi ? : Routage des messages.
• A la fin de l’exécution de l’algorithme, chaque nœud ni est informé :
• de la plus petite distance qui le sépare de chaque nœud du réseau
• du plus court chemin qui relie ni à à un autre nœud nj.
• Pour le chemin (ni, nj): ni connaît le voisin nk qui appartient au
chemin. nk connaît à son tour le prochain voisin direct nh qui le relie à
nj, et ainsi de suite.
• Deux algorithmes :
• Algorithme synchrone : S_Calcul_PCC
• Algorithme asynchrone : A_Calcul_PCC

69

Algorithme Synchrone :
S_Calcul_PCC

disti (j) : la plus petite distance qui sépare le nœud ni du nœud nj

• A l’instant t = 0 : Chaque nœud ni envoie son identificateur à tous ses

voisins.
• A l’instant t = 1 :
• Chaque nœud ni a reçu les messages de la part de ses voisins, il connaît
alors les nœuds nj tels que disti(j) = 0 ou 1.
• ni construit l’ensemble des nœuds nj tels que disti (j)= 1 et les transmets
vers ses voisins.
• A l’instant t = 2 :
• Chaque nœud ni a reçu les messages de la part de ses voisins, il connaît
alors les nœuds nj tels que disti(j) = 0, 1 ou 2.
• ni construit l’ensemble des nœuds nj tels que disti(j)=2 et les transmets
vers ses voisins.

70
 Algorithme Synchrone :
S_Calcul_PCC

• A l’instant t >= 0, chaque nœud ni envoie à ses voisins

l’ensemble des nœuds nj tels que la distance disti (j) = t.

• Pour t = 0, cet ensemble est le singleton ni.

• Pour t > 0, cet ensemble représente les nœuds reçus

durant les précédents t–1 instants. La distance entre ces
nœuds et ni est au plus égale à t:
• Ces nœuds ont une distance t-1 des voisins de ni.

71

Structure de données (S_Calcul_PCC)

• disti (j) : la plus petite distance qui sépare le nœud ni du

nœud nj
• Initialement, disti (j) = n pour i ≠ j et disti (i) = 0.
• firsti (j) : nœud, appartenant à vi, qui est le premier nœud
du chemin le plus court qui relie les nœuds ni et nj.
• Initialement, firsti(k)= null
• seti (t) : L’ensemble des nœuds que ni envoie à ses
voisins à l’instant t.
• Initialement, seti (0) = {ni}
• MSGi (t) : Ensemble des nœuds reçus par le nœud ni à
l’instant t-1 de la part de tous les nœuds voisins
• MSGi (t) est l’union des messages setj (t) reçus de la part des
voisins nj du nœud ni.
72
 Algorithme : S_Calcul_PCC
• MSGi (0) = {} ;
• Pour (tous les nœuds de N) faire envoyer seti(0) aux voisins vi finpour •seth(t-1)
• Pour t allant de 1 à n – 1 faire // longueur max d’un chemin = n -1
• Pour (chaque réception de MSGi(t-1)) faire setm(t-1) •setl(t-1)
• seti(t) = {} ;
• Pour (chaque setj(t-1) appartenant à MSGi(t-1)) faire MSGi(t-1)
• Pour chaque nœud nk appartenant à setj(t-1) faire

• Si (disti (k) > t) alors

• disti (k) = t ;
• firsti (k) = nj; seti(t)
ni
• seti(t) = seti(t)+{nk}
• Finpour

• Envoyer seti(t) à tous les voisins de ni (ensemble vi)

• t = t + 1;
• Finpour
• FinPour
73

Version asynchrone …

74
 Structure de données (A_Calcul_PCC)

• disti (j) : la plus petite distance qui sépare le nœud ni du

nœud nj
• Initialement, disti (j) = n pour i ≠ j et disti (i) = 0.
• leveli (j) = d : ni a reçu de nj les nœuds ayant une distance
d de nj.
• nj appartient à vi
• Initialement, leveli(j)= -1
• leveli (j) peut être considéré comme l’horloge par
rapport au voisin nj
• firsti (j) : nœud, appartenant à vi : le premier nœud du
chemin le plus court qui relie les nœuds ni et nj.
• Initialement, firsti(j)= null
75

Structure de données (A_Calcul_PCC)

• statei : statei = d signifie que ni a reçu tous les

identificateurs des nœuds qui sont à une distance d.

• Initialement, statei = 0

• statei peut être considérée comme l’horloge des

«horloges» leveli (j) (en ce qui concerne le nœud ni)

• seti : Nœuds à envoyer par ni à ses voisins.

• Initialement, seti = {ni}

76
 Structure de données (A_Calcul_PCC)

• Pour tous les nœuds ni

• disti (i) = 0;
• disti (j) = n pour j ≠ i
• leveli (j) = -1 pour ni appartenant à vi.
• firsti (j) = null pour i ≠ j
• statei = 0
• initi = faux
• seti = {ni}
• Pour les nœuds ni appartenant à No
• initi = vrai
• Envoyer seti à tous les nœuds voisins (vi)

77

Algorithme A_Calcul_PCC
(exécuté par tous les ni)

• Tant que (statei < n-1) faire

• A la réception d’un message setj de la part de nj
(appartenant à vi)
• Si (non initi) alors debut initi = vrai; envoyer seti à tous les voisins
fin fsi
• leveli (j) = leveli (j) + 1;
• Pour (tous les nœuds nk appartenant à setj) faire
• Si (disti (k) > leveli (j) + 1) alors
• disti (k) = leveli (j) + 1 ;
• firsti (k) = nj;
• Si (leveli (j) >= statei) pour tous les nj de l’ensemble vi) alors
• statei = statei + 1;

• seti = {nk / disti(k) = statei}

• Envoyer seti à tous les voisins de ni (ensemble vi)
78
 Plan

• Hypothèses de travail
• Généralités
• Collecte (Convergecast)
• Diffusion (Broadcast)
• Construction d’arbres de recouvrement
• Identification des noeuds d’un réseau
• Calcul du plus court chemin
• Algorithme d’élection
• Algorithmes de recherche
79

Algorithmes d’élection

• On s’intéresse aux graphes complets

• 1ère solution
• Tous les nœuds envoient leur identifiants aux autres nœuds
• A la réception des identifiants, chaque nœud peut identifier le
nœud leader
• Complexité : O(n2) pour les messages et O(1) pour le
traitement

80
 Algorithme S_Elect_Leader

• 2ème solution
• Les nœuds candidats sont ceux qui désirent être leaders
• Chaque nœud envoie son identifiant (id) à un seul (20)
destinataire, puis à 2 (21) destinataires, puis à 4 (22)
destinataires, etc.
• Lors de la kéme étape, un nœud envoie son id à 2k-1
destinataires
• Pour envoyer à tous les nœuds, il faut log(n) étapes
• Complexité
• O(n log(n)) pour les messages
• O(n) pour le traitement

81

Algorithme S_Elect_Leader

• 2ème solution … suite

• L’envoie de l’id est considéré comme une tentative de
«capture» du nœud destinataire
• Pour être élu, il faut réussir à capturer tous les nœuds du
réseau
• Un nœud ni réussit à capturer un nœud nj si idi est plus
grand que les id de tous les nœuds qui tentent de capturer
nj. De plus, idi doit être supérieur à idj.
• A l’étape k, ni ne tente de capturer des nœuds que s’il
réussit à capturer tous les nœuds de l’étape k-1. Dans le
cas contraire, il cesse d’être candidat.

82
 Algorithme d’élection: S_Elect_Leader

• Structure de données
• candidati
• Initialisé à vrai pour les nœuds de No, à faux pour les autres
• triedi(j)
• concerne les nœuds appartenant à vi. Il est à vrai pour les
voisins à qui ni a déjà envoyé un message, faux sinon
• owneri
• Propriétaire du nœud ni, initialisé à NULL

83

Algorithme S_Elect_Leader
(exécuté par tous les ni)

• Initialisation
• t = 0; // horloge ou pulsation
• MSGi = {};
• Pour les nœuds candidats (appartenant à No), faire
• candidati = true

• owneri = idi

• Choisir un nœud nj de vi

• Envoyer capture(idi) à nj

• t = t + 1;

84
 Algorithme S_Elect_leader
(exécuté par tous les ni)

• t impair:
• Recevoir MSGi //union des captures reçus
• Sélectionner nk tel que idk >= idj, nj étant les nœuds
qui ont envoyé une demande de capture à ni.
• Si owneri < idk alors
• Si candidati alors candidati = faux;
• owneri = idk
• Envoyer ACK à nk
• t = t + 1;

85

Algorithme S_Elect_Leader
(exécuté par tous les ni)

• t est pair:
• Recevoir MSGi //union des ACK reçus
• Si candidati alors
• Si «le nombre de messages envoyés (captures) est supérieur
(strictement) à celui des ACK reçus»
• alors candidati = faux;

• sinon

• Si t < 2 (log n) alors

• Sélectionner parmi les nœuds nj de vi un ensemble S

tels que leur triedi(j) = faux
• Mettre triedi(j) à vrai pour les éléments de S
• Envoyer capture(idi) aux éléments de S
• t = t + 1;
86
 Version asynchrone …

87

Algorithme asynchrone
A_Elect_Leader

• L’algorithme doit s’assurer que deux candidats ne

doivent/peuvent jamais capturer un même nœud
• Un nœud a toujours un seul et unique leader (propriétaire)
• La comparaison ne se fait pas en fonction des identifiants
id mais en fonction du niveau d’avancement «level»
• level : nombre de groupes capturés par le nœud: 1, 2, 4,
8, etc.
• leveli = E [log (ownsi + 1)] où ownsi est le nombre de nœuds
capturés par ni

88
 A_Elect_Leader : comment ça marche?

• Pour capturer nj, ni envoie un message:

• capture (leveli, idi )
• A la réception de ce message, nj teste:
• (levelj, propriétairej ) < (leveli, idi )
• Test lexicographique: si les variables levels sont identiques, on
compare les variables propriétairej et idi.

89

A_Elect_Leader : comment ça marche?

• ni demande la capture de nj :
• ni envoie à nj un message capture (leveli, idi )
• A la réception de ce message, nj effectue le test:
• Si (levelj, propriétairej) > (leveli, idi ) alors
• nj envoie un message nack à ni
• Sinon
• levelj = leveli
• Si nj est candidat
• nj n’est plus candidat
• nj envoie un message ack à ni
• A la réception du message ack, ni devient le propriétaire de nj.

90
 A_Elect_Leader : comment ça marche?

• Si nj n’est pas candidat

• p_propriétairej = ni //garder trace de la candidature de ni
• nj envoie un message check (k) à ni
• nk est le propriétaire actuel de nj.
• Objectif: Régler le contentieux entre ni et nk.
• A la réception du message check, ni (s’il est toujours
candidat):
• Envoie un message eliminate (leveli, idi) à nk.
• A la réception du message eliminate (leveli, idi), nk teste :
• Si (levelk, idk ) < (leveli, idi )
• nk envoie un message eliminated à ni
• Sinon
• nk envoie un message nack à ni

91

A_Elect_Leader : Algorithme

• Structure de données
• candidati
• Initialisé à vrai pour les nœuds de No, à faux pour les autres
• triedi(j)
• concerne les nœuds appartenant à vi. Il est à vrai pour les voisins à
qui ni a déjà envoyé un message de capture, faux sinon
• propriétairei
• Propriétaire du nœud ni, initialisé à NULL
• leveli : log (ownsk) nk est le propriétaire de ni
• nb_capturési : nombre de nœuds capturés
• p_proriétairei: proprétaire potentiel du nœud ni
• p_capturéi: nœud en cours de capture par ni

92
 A_Elect_Leader : Algorithme …
suite

• Si ni appartient à No
• candidati = vrai;
• owneri = idi
• ownsi = 0;
• leveli = 0;
• p_owneri = NULL
• p_capturéi = NULL
• On choisit un nœud nj appartenant à vi (vi contient les
autres nœuds du graphe puisque G est complet)
• triedi(j) = vrai
• Envoyer capture (leveli, idi) à nj

93

A_Elect_Leader : Algorithme …
suite

• A la réception de capture (levelj, idj)

• Si p_owner = idj
• owneri = idj
• Envoyer ack () à nj
• Si (leveli, owneri) < (levelj, idj) alors
• leveli = levelj ;
• Si candidati alors
• candidati = faux
• owneri = idj
• Envoyer ack à nj
• Sinon
• p_owneri = idj
• Envoyer check () à nk (propriétaire actuel de ni (owneri = idk))
• Sinon envoyer nack () à nj
94
 A_Elect_Leader : Algorithme …
suite

• A la réception de nack
• Si candidati alors candidati = faux;
• A la réception de check (j)
• Si candidati alors envoyer eliminate (leveli, idi) à nj;

95

A_Elect_Leader : Algorithme …
suite

• A la réception de eliminate (levelj, idj)

• Si non candidati alors envoyer eliminated à nj
• sinon
• Si (leveli, owneri ) < (levelj, idj) alors
• candidati = faux;
• Envoyer eliminated à nj
• Sinon envoyer nack () à nj
• A la réception eliminated
• Si candidati alors
• Soit nj le nœud de vi tel que p_ownedi = idj.
• Send capture (leveli, idi) à nj

96
 A_Elect_Leader : Algorithme …
suite

• A la réception de ack ()
• nb_capturési = nb_capturési + 1;
• leveli = E [log(ownsi )];
• S = {nj appartiennent à vi tels que triedi(j) = faux}
• Si S ≠ {} alors
• On choisit un nœud de S : nj
• triedi (j) = vrai
• Envoyer capture (leveli, idi) à nj

97

Plan
• Hypothèses de travail
• Généralités
• Collecte (Convergecast)
• Diffusion (Broadcast)
• Construction d’arbres de recouvrement
• Identification des noeuds d’un réseau
• Calcul du plus court chemin
• Algorithme d’élection
• Algorithmes de recherche

98
 Gnutella

• Chaque site dispose :

• d’un entrepôt contenant les fichiers partagés
• d’une liste de voisins (au sens Gnutella)
• d’un Algorithme de recherche distribué
• Basé sur un algorithme de diffusion
• Avec une portée limitée (Time To Live : TTL)

Principe de recherche
• Une requête de recherche :
• Fichier recherché,
• Durée de vie (Time To Live : TTL)

• Une requête est envoyée vers les nœuds voisins

• A la réception d’une requête :
• Recherche dans l’entrepôt local
• Si le fichier existe, un relpy est envoyé à l’émetteur
• Décrémentation de TTL
• Si TTL non nul, la requête est envoyée aux voisins
directs.
Principe de recherche

•Site Gnutella
•Site Gnutella •3 •Client
•2
•3
•Site Gnutella
•2
•1 •Site Gnutella •3
•2
•Site Gnutella
•2
•Connexion Gnutella
•Fichier trouvé •Site Gnutella •2 •Site Gnutella
•x •TTL
•1

FreeNet

• Application : partage de données

• Chaque site dispose de :
• son propre entrepôt
• Un algorithme de recherche

• Un fichier est représenté par :

• Une clé
• Son contenu (pas toujours)
• L’adresse IP de la machine qui l’héberge (propriétaire)
Entrepôt

Clé Contenu (donnée) Adresse IP

(propriétaire)
xYWERaa Pointeur sur le fichier [Link]

saWQEa Pointeur sur le fichier [Link]

Réseau Freenet

•67 c
•55 b
•10 e •c
•55 b •67 c

•a •b •50 d
•98 d

•d
•Connexion Freenet

•f
•e •45 f
•45 f •98 d
•55 b •10 e
 Principe de la recherche

• A la réception d’une requête :

• Recherche du fichier (clé) dans l’entrepôt local
• Envoie au voisin qui héberge le fichier ayant la clé la
plus proche
• Un site ne traite jamais une requête plus qu’une fois.
• Lorsqu’un site ne peut plus transmettre une requête, il la
renvoie au site émetteur …
• Le résultat est :
• transmis au client en suivant le même circuit
• stocké au niveau des sites intermédiaires

Algorithme de recherche
•Recherche d’un document : clé = 50
•50 d •67 c
•55 b
•50 d •10 e •c
•55 b •67 c •2
•1 •3
•a •b •50 d
•Requête •98 d
•12
•11 •d
•7 •6 •4 •9
•Réponse positive
•Requête •10
•Réponse négative •f •5
•e •45 f
•Connexion Freenet •8
•45 f •98 d
•55 b •10 e
•50 d