===== 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|]]