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

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

A la réception d'un El\left(c_k,k\right) un processus P_i répond

• Ack(i) à P_k si sa capacité c_i est inférieur ou égale à c_k
• El\left(c_i,i\right) en diffusion si sa capacité est strictement supérieur à c_k

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

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 : \displaystyle 1 + (k-1) + (k-2) + ... + 1 = 1+ \sum_{i=1}^{k-1} i = \frac{\left(k-1\right)k}{2}+1
  • n-1 messages envoyés par élection (ou diffusion, plus exactement).
  • total messages : élections * msg/élection = \displaystyle \left(\frac{\left(k-1\right)k}{2}+1 \right) \times \left(k-1\right)=O\left(k^3\right), maximisé lorsque k=N, le rang du plus faible.
• Quant aux acquittements, : à terminer, mes notes sont un peu légères en cette partie.

• 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.

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?

Elections (2/2) – algo_dist_4