Différences

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|]]
 
m1ilc/algo_dist_2.txt · Dernière modification: 2010/01/10 17:21 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki