Election dans un graphe quelconque

Maillage complet et diffusion

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
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 : \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, 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

 
m1ilc/algo_dist_3.txt · Dernière modification: 2010/01/08 12:54 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