Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

m1ilc:algo_dist_1 [2010/01/10 16:28]
suitable
m1ilc:algo_dist_1 [2010/01/10 16:51] (Version actuelle)
suitable
Ligne 93: Ligne 93:
 <pagebreak> <pagebreak>
  
-=== Solution #2 ===+=== Election sur un arbre couvrant ===
  
 +=== Remarques Préalables ===
 +
 +Il est coutume de distinguer trois "solutions" à ce problème:
 +  * l'initiateur est la racine
 +  * l'initiateur demande à la racine de conduire l'élection pour lui
 +  * l'initiateur (et le protocole) ne s'appuient pas sur le rôle de la racine.
 +
 +Topologiquement, si l'on oublie les notions de parent et fils et les remplace (initialement) par la notion fusionnelle //voisins//, tout processus peut être vu comme la racine d'une élection qu'il initie. Après, le processus duquel chaque processus reçoit le message ELECTION est logiquement son parent vis-àvis de ce scrutin, et ses autres //voisins// sont logiquement ses fils //pour ce scrutin//.  Mais puisqu'il peut être difficile d'exprimer le protocole en ces termes inhabituels, on explicitera chaque fois "s'il recoit de son parent...s'il recoit d'un fils, il fait pour tous les autre fils mais pas le fils source...etc"
 + 
 == Prémisses == == Prémisses ==
  
Ligne 102: Ligne 111:
 == Principes == == Principes ==
  
-  * le site initiateur envoie un jeton de sondage à chacun de ses voisins, et crée une liste pour contrôler les remontées.+  * le site initiateur envoie un <del>jeton</del> message de sondage à chacun de ses voisins ((s'il est la racine, à ses fils; s'il est feuille, à sont parent; autrement, au deux)), et crée une liste pour contrôler les remontées.
   * à réception, chaque site    * à réception, chaque site 
-    * change le jeton si sa capacité est supérieur+    * change le <del>jeton</del>message si sa capacité est supérieur
     * continue la diffusion s'il peut (il n'est pas feuille)     * continue la diffusion s'il peut (il n'est pas feuille)
     * remonte sa réponse s'il est feuille, ou si tous ses dépendants lui ont répondu, ayant sélectionnée la plus forte réponse au fur et à mesure que ses dépendants lui ont répondu.     * remonte sa réponse s'il est feuille, ou si tous ses dépendants lui ont répondu, ayant sélectionnée la plus forte réponse au fur et à mesure que ses dépendants lui ont répondu.
Ligne 114: Ligne 123:
 == Initialisation == == Initialisation ==
  
-  - <jsm>P_{i_0}</jsm> transmet le jeton [ <jsm>"election";c_{i_0},i_0; i_0</jsm> ] à tous ses voisins, tout en créant une liste de ceux-ci pour pouvoir pointer les remontées.+  - <jsm>P_{i_0}</jsm> transmet le <del>jeton</del>message [ <jsm>"election";c_{i_0},i_0; i_0</jsm> ] à tous ses voisins, tout en créant une liste de ceux-ci pour pouvoir pointer les remontées.
  
 == Reception == == Reception ==
  
-Lorsque <jsm>P_j</jsm> reçoit un jeton [ <jsm>"election";c_{i},i; \underbrace{i_0,...}_{pile}</jsm> ]:+Lorsque <jsm>P_j</jsm> reçoit un <del>jeton</del>message [ <jsm>"election";c_{i},i; \underbrace{i_0,...}_{pile}</jsm> ]:
  
   * Si <jsm>P_i \notin</jsm> pile => il s'agit d'une diffusion et non une remontée.   * Si <jsm>P_i \notin</jsm> pile => il s'agit d'une diffusion et non une remontée.
     * si <jsm>c_j \gt c_i</jsm> alors il modifie le jeton tel:[ <jsm>"election";c_j,j; i_0,...,j</jsm> ]     * si <jsm>c_j \gt c_i</jsm> alors il modifie le jeton tel:[ <jsm>"election";c_j,j; i_0,...,j</jsm> ]
-    * sinon, il modifie le jeton tel : [ <jsm>"election";c_i,i; i_0,...,j</jsm> ]+    * sinon, il modifie le <del>jeton</del>message tel : [ <jsm>"election";c_i,i; i_0,...,j</jsm> ]
     * s'il est feuille, il renvoie à son prédécesseur dans la file     * s'il est feuille, il renvoie à son prédécesseur dans la file
       * sinon, il transmet à tous ses voisins hormis son prédécesseur dans la pile (celui duquel il a reçu la demande), et crée une liste pour pointer les remontées.       * sinon, il transmet à tous ses voisins hormis son prédécesseur dans la pile (celui duquel il a reçu la demande), et crée une liste pour pointer les remontées.
 
m1ilc/algo_dist_1.txt · Dernière modification: 2010/01/10 16:51 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