Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
— |
m1ilc:algo_dist_2 [2010/01/10 17:21] (Version actuelle) suitable créée |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ===== Elections (2/2) ===== | ||
+ | ==== Election sur un arbre couvrant (suite) ==== | ||
+ | |||
+ | ==== Racine initiateur ==== | ||
+ | |||
+ | === Hypothèses === | ||
+ | |||
+ | * L'initiateur, <jsm>P_{i_0}</jsm> est la racine | ||
+ | * Communications FIFO, sans perte, par arbre couvrant | ||
+ | |||
+ | === Principe === | ||
+ | |||
+ | * <jsm>P_{i_0}</jsm> envoie REQ à tous ses fils, pour choisir quand toutes les réponse seront remontées. | ||
+ | * Chaque fils qui n'est pas feuille transmet à ses fils. | ||
+ | * Lorsqu'un processus aura reçu les réponses de tous ses fils, il répondra à son parent la meilleur valeur de ses fils et de lui-même. | ||
+ | * Lorsque <jsm>P_{i_0}</jsm> a reçu toutes les réponse, il connait la meilleur capacité et chez qui, et proclame. | ||
+ | |||
+ | === Corrigé (du support de cours) === | ||
+ | |||
+ | * Phase I - Initialisation | ||
+ | * <jsm>P_{i_0}</jsm> émet le message //ElDemande()// vers tous ses fils | ||
+ | * lorsqu'un site //non feuille// reçoit le message, il transmet ce message à l'ensemble de ses fils. | ||
+ | * lorsqu'un site //feuille// <jsm>P_{j}</jsm> reçoit le message //ElDemande()// il transmet à son père les message <jsm>EL\left(c_j, j\right)</jsm> | ||
+ | * Phase 2 - Remontée des informations | ||
+ | * lorsqu'un site <jsm>P_{i\ne i_0}</jsm> a reçu tous les messages <jsm>El\left(c_j, j\right)</jsm> de ces fils, il transmet à son père le message <jsm>EL\left(c_k, k\right)</jsm> où <jsm>c_k = \max\left\{c_i, c_j\right\}</jsm> | ||
+ | * Phase 3 - Election | ||
+ | *Lorsque le site <jsm>P_{i_0}</jsm> a reçu tous les messages <jsm>EL\left(c_k, k\right)</jsm> de ses fils, il s'élit si <jsm>max\left\{ c_k\right\} < c_{i_0} </jsm> sinon il élit <jsm>P_k</jsm> tel que <jsm>c_k</jsm> = <jsm>max\left\{ c_k \right\} </jsm> | ||
+ | * **Phase 4 - Proclamation ** | ||
+ | * La racine proclame le résultat par l'émission du message //ELU(k)// vers l'ensmeble de ses fils. | ||
+ | *Lorsqu'un site reçoit le message //ELU(k)// il mémorise l'information puis s'il est non-feuille, il transmet ce message //ELU(k)// à tous ses fils. | ||
+ | |||
+ | ==== Initiateur n'est pas la racine === | ||
+ | |||
+ | |||
+ | ==== Election dans un réseau quelconque ==== | ||
+ | |||
+ | === Maillage complèt et diffusion === | ||
+ | |||
+ | |||
+ | ==== Navigation ==== | ||
+ | |||
+ | [[algo_dist_1|]] -- [[algo_dist_3|]] |