==== Election dans un graphe quelconque ====

=== Maillage complet et diffusion ===

Soit l'algorithme du plus fort (bully algorithme) de Garcia-Molina:

Le site initiateur <jsm>P_{i_0}</jsm> diffuse le message <jsm>El\left(c_{i_0},i_0\right)</jsm> à tous les processus. Puis il attend.

A la réception d'un <jsm>El\left(c_k,k\right)</jsm> un processus <jsm>P_i</jsm> répond
  * Ack(i) à <jsm>P_k</jsm> si sa capacité <jsm>c_i</jsm> est inférieur ou égale à <jsm>c_k</jsm>
  * <jsm>El\left(c_i,i\right)</jsm> en diffusion si sa capacité est strictement supérieur à <jsm>c_k</jsm>

    - Appliquer l'algorithme sur l'exemple suivant : c1=5, c2=Y, c3=9, où P1 initie l'éléction.
    - Quel est le pire des cas (en terme de messages échangés)?
    - Même question pour N processus

^ De ^ Message ^ A ^ Pourquoi ^
| P1 | El(5,1) | P2 |  Init  |
| P1 | El(5,1) | P3 |  Init  |
| P2 | El(7,2) | P1 |  El de P1 |
| P2 | El(7,2) | P3 |  El de P1 |
| P3 | El(9,3) | P1 |  El de P1 |
| P3 | El(9,3) | P2 |  El de P1 |
| P1 | Ack(1)  | P2 |  El de P2 |
| P1 | Ack(1)  | P3 |  El de P3 |
| P2 | Ack(2)  | P3 |  El de P3 |
| P3 | El(9,3) | P1 |  El de P2 |
| P3 | El(9,3) | P2 |  El de P2 |
| P1 | Ack(1)  | P3 |  El de P3 |
| P2 | Ack(2)  | P3 |  El de P3 |

On a des élections en cascade et à répétition parce que les sites reposent la question aux sites qui ont déjà répondu ''Ack''. Qui plus est, il n'y a pas de mécanisme pour déclencher Proclamation : faut dire que le site qui reçoit ''Ack'' de tous les autres sites soit proclame "c'est moi le plus fort!", soit dit à l'initiateur de le faire.

Pire des cas : le site le plus faible initie. Voyons pourquoi :

  * Lorsque le site le plus fort diffuse une élection, 
    * il envoie N-1 messages, 
    * il reçoit N-1 ''Ack''.
    * => 1 élection
  * Lorsque c'est le deuxième plus fort, 
    * il envoie N-1 messages, 
    * il reçoit N-2 ''Ack'',
    * mais il fait diffuser une élection par #1 (le plus fort), donc N-1 messages de plus et N-1 ''Ack'' (dont le sien).
    * => 2 élections
  * De même, le 3e diffuse une élection qui entrainera des élections diffusées par #1 et #2, et celle de #2 entrainera une autre de #1.
    * => 4 élections
  * Si le k-ième site diffuse une élection, il en suivra k-1 autres qui entraineront k-2 autres, et ainsi de suite jusqu'à une dernière diffuser par #1:
    * nombre d'élections si ''k'' initie : <jsm>\displaystyle 1 + (k-1) + (k-2) + ... + 1 = 1+ \sum_{i=1}^{k-1} i = \frac{\left(k-1\right)k}{2}+1</jsm>
    * <jsm>n-1 </jsm> messages envoyés par élection (ou diffusion, plus exactement).
    * total messages : élections  * msg/élection = <jsm>\displaystyle \left(\frac{\left(k-1\right)k}{2}+1 \right) \times \left(k-1\right)=O\left(k^3\right)</jsm>, maximisé lorsque k=N, le rang du plus faible.
  * Quant aux acquittements, FIXME : à terminer, mes notes sont un peu légères en cette partie.

=== Completer l'Algorithme ===

  * Lorsqu'un site aura reçu Ack() de tous les autres sites, il Proclame()
  * Lorsque l'initiateur aura soit Proclamé, soit reçu la proclamation, il informe le demandeur.

=== Réduire le Trafic ===

Pour réduire le nombre de messages:
  * solution radicale : on ne cascade pas les élections, on répond à l'initiateur--un seul aller-retour. Mais là on abandonne l'esprit du protocole, non?
  * empêcher les sites de diffuser l'élection après avoir émis un ''Ack()'' car il ne peut pas être le futur gagnant -- combien ça réduit?


==== Navigation ====

[[algo_dist_2|]] -- [[algo_dist_4|]]